Maximum Cardinality Simple 2-matchings in Subcubic Graphs

DOI10.1137/090760416MaRDI QIDQ3105789zbMATH OpenOpenAlexFDO

Authors Yanjun Li, David 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 optimizationmatchingstraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• Maximum cardinality 1-restricted simple 2-matchings
• Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)
• Subgraphs of maximum matching graphs
• A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs
• On Lower Bounds for the Matching Number of Subcubic Graphs
• A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• Minimum maximal matchings in cubic graphs
• Capacities of graphs and \(2\)-matchings
• Induced matchings in subcubic graphs

Cited in

(21)

• Maximum cardinality 1-restricted simple 2-matchings
• The parity Hamiltonian cycle problem
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges
• Positive planar satisfiability problems under 3-connectivity constraints
• Decomposition theorems for square-free 2-matchings in bipartite graphs
• The traveling salesman problem on cubic and subcubic graphs
• Decomposition theorems for square-free 2-matchings in bipartite graphs
• The parity Hamiltonian cycle problem in directed graphs
• TSP on cubic and subcubic graphs
• Terminal backup, 3D matching, and covering cubic graphs
• Restricted b-matchings in degree-bounded graphs
• A proof of Cunningham's conjecture on restricted subgraphs and jump systems
• Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids
• The nonnegative node weight \(j\)-restricted \(k\)-matching problems
• Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)
• Matchability and \(k\)-maximal matchings
• Finding triangle-free 2-factors in general graphs
• Another proof of the generalized Tutte-Berge formula for f-bounded subgraphs
• Finding a maximum restricted t-matching via Boolean edge-CSP
• Finding a maximum restricted \(t\)-matching via Boolean edge-CSP

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3105789)