Maximum Cardinality Simple 2-matchings in Subcubic Graphs

DOI10.1137/090760416zbMath1230.90160OpenAlexW2002065932MaRDI QIDQ3105789

Yanjun Li, David B. Hartvigsen

Publication date: 9 January 2012

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090760416

zbMATH Keywords

combinatorial optimizationtraveling salesman problemmatchings

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

Positive planar satisfiability problems under 3-connectivity constraints ⋮ 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 ⋮ The parity Hamiltonian cycle problem ⋮ Polyhedron of triangle-free simple 2-matchings in subcubic graphs ⋮ A proof of Cunningham's conjecture on restricted subgraphs and jump systems ⋮ The traveling salesman problem on cubic and subcubic graphs ⋮ TSP on Cubic and Subcubic Graphs ⋮ A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges ⋮ Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs ⋮ The Parity Hamiltonian Cycle Problem in Directed Graphs ⋮ The Nonnegative Node Weight j-Restricted k-Matching Problems

This page was built for publication: Maximum Cardinality Simple 2-matchings in Subcubic Graphs