The Library
First steps in combinatorial optimization on graphons : matchings
Tools
Dolezal, Martin, Hladký, Jan, Hu, Ping and Piguet, Diana (2017) First steps in combinatorial optimization on graphons : matchings. Electronic Notes in Discrete Mathematics, 61 . pp. 359-365. doi:10.1016/j.endm.2017.06.060 ISSN 1571-0653.
|
PDF
WRAP-first-steps-combinatorial-optimization-graphons-matchings-Hu-2017 (1).pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (481Kb) | Preview |
Official URL: https://doi.org/10.1016/j.endm.2017.06.060
Abstract
Much of discrete optimization concerns problems whose underlying structures are graphs. Here, we translate the theory around the maximum matching problem to the setting of graphons. We study continuity properties of the thus defined matching ratio, limit versions of matching polytopes and vertex cover polytopes, and deduce a version of the LP duality for the problem of maximum fractional matching in the graphon setting.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Combinatorial optimization, Matching theory, Graph theory | ||||||
Journal or Publication Title: | Electronic Notes in Discrete Mathematics | ||||||
Publisher: | Elsevier BV | ||||||
ISSN: | 1571-0653 | ||||||
Official Date: | 3 August 2017 | ||||||
Dates: |
|
||||||
Volume: | 61 | ||||||
Page Range: | pp. 359-365 | ||||||
DOI: | 10.1016/j.endm.2017.06.060 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Description: | Proceedings of Eurocomb'17 |
||||||
Date of first compliant deposit: | 4 August 2017 | ||||||
Date of first compliant Open Access: | 3 August 2018 | ||||||
Funder: | Leverhulme Trust (LT), European Research Council (ERC) | ||||||
Grant number: | 648509 (ERC) |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year