First steps in combinatorial optimization on graphons: matchings

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