Edmonds polytopes and weakly hamiltonian graphs

DOI10.1007/BF01580109zbMath0267.05118OpenAlexW2072789827WikidataQ59699138 ScholiaQ59699138MaRDI QIDQ5685112

Václav Chvátal

Publication date: 1973

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580109

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Linear inequalities of matrices (15A39) Polytopes and polyhedra (52Bxx)

Related Items

Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Balanced vehicle routing: polyhedral analysis and branch-and-cut algorithm, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), A branch-and-cut algorithm for the preemptive swapping problem, Generalized multiple depot traveling salesmen problem -- polyhedral study and exact algorithm, Multi-depot multiple TSP: a polyhedral study and computational results, On cutting-plane proofs in combinatorial optimization, A note on the polytope of bipartite TSP, A matching problem with side conditions, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, Discrete extremal problems, Polyhedron of triangle-free simple 2-matchings in subcubic graphs, The symmetric quadratic traveling salesman problem, Sensitivity theorems in integer linear programming, Chvátal closures for mixed integer programming problems, Recent advances in vehicle routing exact algorithms, The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities, On approximating the longest path in a graph, George Dantzig's contributions to integer programming, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Polyhedral study of the capacitated vehicle routing problem, On symmetric subtour problems, Partial linear characterizations of the asymmetric travelling salesman polytope, Lineare Charakterisierungen von Travelling Salesman Problemen, Exact algorithms for routing problems under vehicle capacity constraints, Branch and cut methods for network optimization, On the symmetric travelling salesman problem I: Inequalities, On the symmetric travelling salesman problem II: Lifting theorems and facets, The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization, Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint), On the complexity of cutting-plane proofs, A survey of some network reliability analysis and synthesis results, Understanding cutting planes for QBFs, Certification of an optimal TSP tour through 85,900 cities, A computational comparison of flow formulations for the capacitated location-routing problem, A note on Hamiltonian split graphs, The graphical relaxation: A new framework for the symmetric traveling salesman polytope, Cutting-plane proofs in polynomial space, Edmonds polytopes and a hierarchy of combinatorial problems, Recent trends in combinatorial optimization, The complexity of facets (and some facets of complexity), Optimizing over the subtour polytope of the travelling salesman problem

Cites Work

• Unnamed Item
• Unnamed Item
• Edmonds polytopes and a hierarchy of combinatorial problems
• Tough graphs and Hamiltonian circuits.
• Maximum matching and a polyhedron with 0,1-vertices
• Cycles and Connectivity in Graphs
• The Factors of Graphs