scientific article; zbMATH DE number 3609444

zbMath0392.90045MaRDI QIDQ4174517

Martin Grötschel

Publication date: 1977

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Travelling Salesman ProblemCombinatorial OptimizationNp-Completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Exact enumeration problems, generating functions (05A15) Integer programming (90C10) Linear programming (90C05) Permutations, words, matrices (05A05) Enumeration in graph theory (05C30) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Boolean programming (90C09) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Applications of graph theory to circuits and networks (94C15)

Related Items (26)

Clique tree inequalities define facets of the asymmetric traveling salesman polytope ⋮ Complete linear descriptions of small asymmetric traveling salesman polytopes ⋮ Solving the max-cut problem using eigenvalues ⋮ Distance conserving reductions for nonoriented networks ⋮ The facets of the spanning trees polytope ⋮ On cutting-plane proofs in combinatorial optimization ⋮ Characterizations of adjacency on the branching polyhedron ⋮ On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets ⋮ Adjacent vertices on the b-matching polyhedron ⋮ The symmetric traveling salesman problem and edge exchanges in minimal 1- trees ⋮ Euclidean semi-matchings of random samples ⋮ The facets of the asymmetric 5-city traveling salesman polytope ⋮ The prize collecting traveling salesman problem ⋮ Lineare Charakterisierungen von Travelling Salesman Problemen ⋮ Facets of the \((s,t)-p\)-path polytope ⋮ Minimum cut bases in undirected networks ⋮ The perfectly matchable subgraph polytope of a bipartite graph ⋮ On the symmetric travelling salesman problem I: Inequalities ⋮ On the symmetric travelling salesman problem II: Lifting theorems and facets ⋮ A polyhedral study of the asymmetric traveling salesman problem with time windows ⋮ Matroid optimization problems with monotone monomials in the objective ⋮ A cutting plane algorithm for minimum perfect 2-matchings ⋮ Optimum matching forests III: Facets of matching forest polyhedra ⋮ Cost-oriented assembly line balancing: model formulations, solution difficulty, upper and lower bounds ⋮ Halin graphs and the travelling salesman problem ⋮ A cutting plane procedure for the travelling salesman problem on road networks

This page was built for publication: