Name
Abstract | ||
|---|---|---|
AbstractLet G = V , E be a graph. The matching polytope of G , denoted by P G , is the convex hull of the incidence vectors of all matchings in G . As proved by Edmonds [10] [Edmonds J 1965 Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards Sect. B 691-2:125-130.], P G is determined by the following linear system π G : x e â 0 for each e ∈ E ; x δ v â 1 for each v ∈ V ; and x E [ U ] â ï | U |â for each U â V with | U | odd. In 1978, Cunningham and Marsh [6] [Cunningham W, Marsh A 1978 A primal algorithm for optimum matching. Balinski ML, Hoffman AJ, eds. Polyhedral combinatorics . Mathematical Programming Studies, Vol. 8 Springer, Berlin, 50-72.] strengthened this theorem by showing that π G is always totally dual integral. In 1984, Edmonds and Giles [11] [Edmonds J, Giles R 1984 Total dual integrality of linear inequality systems. Progress in Combinatorial Optimization Academic Press, Toronto, 117-129.] initiated the study of graphs G for which π G is box-totally dual integral. In this paper, we present a structural characterization of all such graphs, and develop a general and powerful method for establishing box-total dual integrality.The online appendix is available at https://doi.org/10.1287/moor.2017.0852 . |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1287/moor.2017.0852 | Periodicals |
Keywords | Field | DocType |
matching,polytope,linear system,box-total dual integrality,signed graph | Discrete mathematics,Mathematical optimization,Combinatorics,Signed graph,Total dual integrality,Polyhedron,Convex hull,Matching (graph theory),Polytope,Linear inequality,Polyhedral combinatorics,Mathematics | Journal |
Volume | Issue | ISSN |
43 | 1 | 0364-765X |
Citations | PageRank | References |
2 | 0.39 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guoli Ding | 1 | 444 | 51.58 |
| Lei Tan | 2 | 84 | 4.27 |
| Wenan Zang | 3 | 305 | 39.19 |