Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus

DOI10.1016/0167-6377(91)90038-QzbMath0748.90045MaRDI QIDQ1180816

A. M. H. Gerards

Publication date: 27 June 1992

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

compact surface\(T\)-join polyhedraexistence of compact systemsperfect matching polyhedra of graphssets of polyhedra

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Linear programming (90C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (5)

Lifts for Voronoi cells of lattices ⋮ Some \(0/1\) polytopes need exponential size extended formulations ⋮ Extended formulations in combinatorial optimization ⋮ Smaller extended formulations for the spanning tree polytope of bounded-genus graphs ⋮ Extended formulations in combinatorial optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On cuts and matchings in planar graphs
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• A new polynomial-time algorithm for linear programming
• The graph genus problem is NP-complete
• A dual ascent approach for steiner tree problems on a directed graph
• Odd Minimum Cut-Sets and b-Matchings
• 2-Matchings and 2-covers of hypergraphs
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Compositions of Graphs and Polyhedra II: Stable Sets
• Matching, Euler tours and the Chinese postman
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus