Number of the records: 1
First steps in combinatorial optimization on graphons: matchings
- 1.0477079 - MÚ 2018 RIV NL eng J - Journal Article
Doležal, Martin - Hladký, J. - Hu, P. - Piguet, Diana
First steps in combinatorial optimization on graphons: matchings.
Electronic Notes in Discrete Mathematics. Roč. 61, August (2017), s. 359-365. ISSN 1571-0653
R&D Projects: GA ČR GA16-07378S; GA ČR GJ16-07822Y
EU Projects: European Commission(XE) 628974 - PAECIDM
Institutional support: RVO:67985840 ; RVO:67985807
Keywords : graphon * graph limits * matching * combinatorial optimization
OECD category: Pure mathematics; Pure mathematics (UIVT-O)
http://www.sciencedirect.com/science/article/pii/S1571065317301452
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.
Permanent Link: http://hdl.handle.net/11104/0273478
File Download Size Commentary Version Access Dolezal2.pdf 3 251.5 KB Publisher’s postprint require
Number of the records: 1