Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem

DOI10.1007/BF02579340MaRDI QIDQ790834zbMATHOpenAlexWikidataFDO

Authors Gérard Cornuéjols, William R. Pulleyblank

Publication date 1983

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

Hamiltonian cycleperfect matching2-matchinghypomatchable

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Applications of graph theory to circuits and networks (94C15)

Recommendations

• The Travelling Salesman Problem in Bounded Degree Graphs
• The traveling salesman problem in bounded degree graphs
• The traveling salesman problem on a graph and some related integer polyhedra
• Relaxed tours and path ejections for the traveling salesman problem
• On the graphical relaxation of the symmetric traveling salesman polytope
• The traveling salesman problem on cubic and subcubic graphs
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• scientific article; zbMATH DE number 3873380
• The traveling salesman problem in graphs with some excluded minors

Cites work

• scientific article; zbMATH DE number 3924538 (Why is no real title available?)
• scientific article; zbMATH DE number 3496213 (Why is no real title available?)
• scientific article; zbMATH DE number 3499169 (Why is no real title available?)
• scientific article; zbMATH DE number 3437188 (Why is no real title available?)
• A matching problem with side conditions
• Maximum matching and a polyhedron with 0,1-vertices
• Minimum node covers and 2-bicritical graphs
• Paths, Trees, and Flowers
• Perfect matchings of a graph
• The Factorization of Linear Graphs
• The Factors of Graphs

Cited in

(21)

• Structural properties of matroid matchings
• Characterizing \(N_+\)-perfect line graphs
• Fractional matchings, component-factors and edge-chromatic critical graphs
• Graph factors and factorization: 1985--2003: a survey
• A construction for non-rank facets of stable set polytopes of webs
• Triangle-free 2-matchings revisited
• A unified combinatorial view beyond some spectral properties
• Packing subgraphs in a graph
• Ear-slicing for matchings in hypergraphs
• Packing $k$-Matchings and $k$-Critical Graphs
• The strength of Dantzig-Wolfe reformulations for the stable set and related problems
• Fractional matchings and the Edmonds-Gallai theorem
• An extension of matching theory
• Small diameter neighbourhood graphs for the traveling salesman problem: At most four moves from tour to tour
• Weighted restricted 2-matching
• Packings by Complete Bipartite Graphs
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• The nonnegative node weight \(j\)-restricted \(k\)-matching problems
• Matchings of cycles and paths in directed graphs
• Relaxed tours and path ejections for the traveling salesman problem
• An Edmonds-Gallai-type decomposition for the \(j\)-restricted \(k\)-matching problem

This page was built for publication: Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q790834)