Adjacency on combinatorial polyhedra

DOI10.1016/0166-218X(94)00092-RzbMath0818.90070MaRDI QIDQ1842660

Sunao Tamura, Tomomi Matsui

Publication date: 4 May 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

set packingperfect matchingset partitioningcombinatorial polyhedravertex packing

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05)

Related Items

On the diameter of cut polytopes, Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope, On the diameter of partition polytopes and vertex-disjoint cycle cover, Ideal polytopes and face structures of some combinatorial optimization problems, Expansion of random 0/1 polytopes, Adjacencies on random ordering polytopes and flow polytopes, Any finite group is the group of some binary, convex polytope, The hierarchy of circuit diameters and transportation polytopes, Weak order polytopes., The common face of some 0/1-polytopes with NP-complete nonadjacency relation, Vertex adjacencies in the set covering polyhedron, The monotonic diameter of traveling salesman polytopes, On the combinatorial structure of the approval-voting polytope

Cites Work

• Unnamed Item
• Unnamed Item
• Signature classes of transportation polytopes
• Algorithms for finding k-best perfect matchings
• Hamiltonicity and combinatorial polyhedra
• The monotonic diameter of the perfect matching and shortest path polytopes
• Adjacency of the best and second best valued solutions in combinatorial optimization problems
• On certain polytopes associated with graphs
• The Hirsch conjecture is true for (0,1)-polytopes
• On the Assignment Polytope
• Simplex pivots on the set packing polytope
• Signature Methods for the Assignment Problem
• The d-Step Conjecture and Its Relatives
• The Monotonic Bounded Hirsch Conjecture is False for Dimension at Least 4
• On the Set-Covering Problem: II. An Algorithm for Set Partitioning
• Two Algorithms for Generating Weighted Spanning Trees in Order
• Set Partitioning: A survey
• The adjacency relation on the traveling salesman polytope is NP-Complete
• Paths, Trees, and Flowers
• Paths on Polyhedra. I
• On the Set-Covering Problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem