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 (18)

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

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