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

DOI10.1007/BF02579340zbMath0535.05038OpenAlexW2053711501WikidataQ29302516 ScholiaQ29302516MaRDI QIDQ790834

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

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

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

Related Items

Fractional matchings and the Edmonds-Gallai theorem, A construction for non-rank facets of stable set polytopes of webs, Packings by Complete Bipartite Graphs, Graph factors and factorization: 1985--2003: a survey, Ear-slicing for matchings in hypergraphs, Fractional matchings, component-factors and edge-chromatic critical graphs, Packing $k$-Matchings and $k$-Critical Graphs, Characterizing N+-perfect line graphs, Packing subgraphs in a graph, Matchings of cycles and paths in directed graphs, Structural properties of matroid matchings, The strength of Dantzig-Wolfe reformulations for the stable set and related problems, An Edmonds-Gallai-type decomposition for the \(j\)-restricted \(k\)-matching problem, Weighted restricted 2-matching, TRIANGLE-FREE 2-MATCHINGS REVISITED, Solving the linear matroid parity problem as a sequence of matroid intersection problems, The Nonnegative Node Weight j-Restricted k-Matching Problems, An extension of matching theory

Cites Work

• A matching problem with side conditions
• Perfect matchings of a graph
• Minimum node covers and 2-bicritical graphs
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• The Factorization of Linear Graphs
• The Factors of Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item