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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.endm.2017.06.060 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
graphon,graph limits,matching,combinatorial optimization | Discrete mathematics,Graph,Combinatorics,Discrete optimization,Matching (graph theory),Combinatorial optimization,Duality (optimization),Polytope,Vertex cover,3-dimensional matching,Mathematics | Journal |
Volume | ISSN | Citations |
61 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 1 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martin Dolezal | 1 | 0 | 0.34 |
Jan Hladký | 2 | 113 | 18.59 |
Ping Hu | 3 | 32 | 4.05 |
Diana Piguet | 4 | 12 | 7.65 |