When Is the Matching Polytope Box-Totally Dual Integral?

References

• Birkhoff G (1946) Three observations on linear algebra (in Spanish). Univ. Nac. Tucumán Ser. A 5:147–151.Google Scholar
• Bondy JA, Murty USR (2008) Graph Theory (Springer, London).Crossref, Google Scholar
• Cameron K (1982) Polyhedral and algorithmic ramifications of antichains. PhD thesis, University of Waterloo, Ontario, Canada.Google Scholar
• Chen X, Chen Z, Zang W (2010) A unified approach to box-Mengerian hypergraphs. Math. Oper. Res. 35(3):655–668.Link, Google Scholar
• Cook W (1986) On box totally dual integral polyhedra. Math. Programming 34(1):48–61.Crossref, Google Scholar
• 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.Crossref, Google Scholar
• Ding G, Feng L, Zang W (2008) The complexity of recognizing linear systems with certain integrality properties. Math. Program. Ser. A 114(2):321–334.Crossref, Google Scholar
• Ding G, Zang W, Zhao Q, On box-perfect graphs. Submitted.Google Scholar
• Ding G, Zang W (2002) Packing cycles in graphs. J. Combin. Theory Ser. B 86(2):381–407.Crossref, Google Scholar
• Edmonds J (1965) Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Nat. Bur. Standards Sect. B 69(1–2):125–130.Crossref, Google Scholar
• Edmonds J, Giles R (1977) A min-max relation for submodular functions on graphs. Ann. Discrete Math. 1:185–204.Crossref, Google Scholar
• Edmonds J, Giles R (1984) Total dual integrality of linear inequality systems. Progress in Combinatorial Optimization (Academic Press, Toronto), 117–129.Crossref, Google Scholar
• Geelen J, Gerards B, Reed B, Seymour P, Vetta A (2009) On the odd-minor variant of Hadwiger’s conjecture. J. Combin. Theory Ser. B 99(1):20–29.Crossref, Google Scholar
• Lovász L, Plummer M (1986) Matching Theory (North-Holland, Amsterdam).Google Scholar
• Papadimitriou C, Yannakakis M (1990) On recognizing integer polyhedra. Combinatorica 10(1):107–109.Crossref, Google Scholar
• Pulleyblank W, Edmonds J (1974) Facets of 1-matching polyhedra. Berge C, Ray-Chaudhuri D, eds. Hypergraph Seminar. Lecture Notes in Mathematics, Vol. 411 (Springer, Berlin), 214–242.Crossref, Google Scholar
• Robertson N, Seymour P (2004) Graph minors. XX. Wagner’s conjecture. J. Combin. Theory Ser. B 92(2):325–357.Crossref, Google Scholar
• Schrijver A (1986) Theory of Linear and Integer Programming (John Wiley & Sons, New York).Google Scholar
• Schrijver A (2003) Combinatorial Optimization—Polyhedra and Efficiency (Springer, Berlin).Google Scholar