Decomposition theorems for square-free 2-matchings in bipartite graphs

DOI10.1016/j.dam.2017.07.035zbMath1372.05176OpenAlexW2745336117MaRDI QIDQ2410265

Kenjiro Takazawa

Publication date: 17 October 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.07.035

zbMATH Keywords

matching theorysquare-free 2-matchingDulmage-Mendelsohn decompositionEdmonds-Gallai decomposition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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, Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs
• Triangle-free 2-matchings and M-concave functions on jump systems
• An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
• A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs
• A proof of Cunningham's conjecture on restricted subgraphs and jump systems
• An algorithm for finding a maximum \(t\)-matching excluding complete partite subgraphs
• 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)
• Improved algorithms for even factors and square-free simple \(b\)-matchings
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• The traveling salesman problem on cubic and subcubic graphs
• Finding maximum square-free 2-matchings in bipartite graphs
• Finding 2-Factors Closer to TSP Tours in Cubic Graphs
• Maximum Cardinality Simple 2-matchings in Subcubic Graphs
• A Weighted k_{t, t}-Free t-Factor Algorithm for Bipartite Graphs
• Coverings of Bipartite Graphs
• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• Restricted b-Matchings in Degree-Bounded Graphs
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• TSP Tours in Cubic Graphs: Beyond 4/3
• Paths, Trees, and Flowers
• Solution of a Large-Scale Traveling-Salesman Problem
• M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
• The Factorization of Linear Graphs
• The Factors of Graphs
• Matrices and matroids for systems analysis