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

DOI10.1007/BF02579340zbMATH Open0535.05038OpenAlexW2053711501WikidataQ29302516 ScholiaQ29302516MaRDI QIDQ790834FDOQ790834

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

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

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)

Cites Work

• Paths, Trees, and Flowers
• The Factorization of Linear Graphs
• Title not available (Why is that?)
• Maximum matching and a polyhedron with 0,1-vertices
• Minimum node covers and 2-bicritical graphs
• Title not available (Why is that?)
• The Factors of Graphs
• A matching problem with side conditions
• Perfect matchings of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (21)

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

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)