Adjacency of the best and second best valued solutions in combinatorial optimization problems

DOI10.1016/0166-218X(93)90128-BzbMath0805.90090MaRDI QIDQ1314336

Akihisa Tamura, Tomomi Matsui, Yoshiko T. Ikebe

Publication date: 31 January 1995

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

zbMATH Keywords

polytopeperfect matchingcombinatorial polytopes\(K\)-best valued extreme pointset packing polytopesset partitioning-polytopesstrong adjacency property

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

The Kth TSP is pseudopolynomial when TSP is polynomial, Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope, Adjacency on combinatorial polyhedra

Cites Work

• Unnamed Item
• Algorithms for finding k-best perfect matchings
• Hamiltonicity and combinatorial polyhedra
• Algorithms for finding a \(K\)th best valued assignment
• Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost