First steps in combinatorial optimization on graphons: matchings

0477079 - MÚ 2018 RIV NL eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR GA16-07378S; GA ČR GJ16-07822Y
GRANT EU: European Commission(XE) 628974 - PAECIDM
Institucionální podpora: RVO:67985840 ; RVO:67985807
Klíčová slova: graphon * graph limits * matching * combinatorial optimization
Obor OECD: 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.
Trvalý link: http://hdl.handle.net/11104/0273478