Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs

DOI10.1016/j.disopt.2017.05.003zbMath1387.90229OpenAlexW2623472667MaRDI QIDQ1751242

Kenjiro Takazawa

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6495/

zbMATH Keywords

traveling salesman problemcombinatorial algorithmmatching theoryHamilton-laceable graphrestricted 2-matchingsubtour elimination constraint

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (4)

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 ⋮ A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges ⋮ Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
• A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
• A proof of Cunningham's conjecture on restricted subgraphs and jump systems
• Combinatorial algorithms for matchings, even factors and square-free 2-factors
• Matching theory
• A matching problem with side conditions
• Restricted \(t\)-matchings in bipartite graphs
• Matching, matroids, and extensions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Worst-case comparison of valid inequalities for the TSP
• Improved algorithms for even factors and square-free simple \(b\)-matchings
• The traveling salesman problem on cubic and subcubic graphs
• An improved upper bound for the TSP in cubic 3-edge-connected graphs
• Finding maximum square-free 2-matchings in bipartite graphs
• Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs
• Finding 2-Factors Closer to TSP Tours in Cubic Graphs
• TRIANGLE-FREE 2-MATCHINGS REVISITED
• A Weighted k_{t, t}-Free t-Factor Algorithm for Bipartite Graphs
• Improved Approximations for Cubic Bipartite and Cubic TSP
• Cycles Intersecting Edge-Cuts of Prescribed Sizes
• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• On Restricted Two-Factors
• Maximal non- hamilton-laceable graphs
• Planar graph colorings without short monochromatic cycles
• TSP Tours in Cubic Graphs: Beyond 4/3
• ${4,5}$ Is Not Coverable: A Counterexample to a Conjecture of Kaiser and Škrekovski
• Paths, Trees, and Flowers
• Solution of a Large-Scale Traveling-Salesman Problem
• Integer Programming and Combinatorial Optimization
• In Pursuit of the Traveling Salesman

This page was built for publication: Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs