Polyhedron of triangle-free simple 2-matchings in subcubic graphs

DOI10.1007/s10107-012-0516-0zbMath1273.05175OpenAlexW2012855576MaRDI QIDQ1949271

Yanjun Li, David B. Hartvigsen

Publication date: 6 May 2013

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-012-0516-0

zbMATH Keywords

traveling salesman problemsubcubic graphpolyhedral characterization2-Matchingsmaximum weight simple 2-matching

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Signed and weighted graphs (05C22)

Related Items

Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles ⋮ Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids ⋮ Decomposition theorems for square-free 2-matchings in bipartite graphs ⋮ When the Gomory-chvátal closure coincides with the integer hull ⋮ Packing $k$-Matchings and $k$-Critical Graphs ⋮ A proof of Cunningham's conjecture on restricted subgraphs and jump systems ⋮ A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges ⋮ Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs ⋮ Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles

Cites Work

• Combinatorial algorithms for matchings, even factors and square-free 2-factors
• A matching problem with side conditions
• The four-colour theorem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Restricted 2-factor polytopes
• Finding maximum square-free 2-matchings in bipartite graphs
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• Maximum Cardinality Simple 2-matchings in Subcubic Graphs
• The traveling salesman problem in graphs with 3-edge cutsets
• On Restricted Two-Factors
• The NP-Completeness of Edge-Coloring
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
• Decomposing 4-Regular Graphs into Triangle-Free 2-Factors
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• Edmonds polytopes and weakly hamiltonian graphs
• The Factorization of Linear Graphs
• A Short Proof of the Factor Theorem for Finite Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item