Edmonds Polyhedra and Weakly Hamiltonian Graphs.
Abstract
Jack Edmonds developed a new way of looking at extremal combinatorial problems and applied his technique with a great success to the problems of the maximal-weight degree-constrained subgraphs. Professor C. St. J. A. Nash-Williams suggested to use Edmonds' approach in the context of hamiltonian graphs. In the present paper, the author determines a new set of inequalities (the comb inequalities) which are satisfied by the characteristic functions of hamiltonian circuits but are not explicit in the straightforward integer programming formulation. A direct application of the linear programming duality theorem then leads to a new necessary condition for the existence of hamiltonian circuits; this condition appears to be stronger than the previously known ones. Relating linear programming to hamiltonian circuits, the present paper can also be seen as a continuation of the work of Dantzig, Fulkerson and Johnson on the travelling salesman problem. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1972
- Accession Number
- AD0740331
Entities
People
- Vaclav Chvatal
Organizations
- Stanford University