Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs

DOI10.1007/978-3-662-53174-7_27zbMath1417.05169OpenAlexW2481690476MaRDI QIDQ2827824

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53174-7_27

zbMATH Keywords

matching theory square-free 2-matching Dulmage-Mendelsohn decomposition Edmonds-Gallai decomposition

Mathematics Subject Classification ID

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

Related Items (1)

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

Cites Work

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
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
A 9/7 -Approximation Algorithm for Graphic TSP in Cubic Bipartite 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
M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
The Factorization of Linear Graphs
Matrices and matroids for systems analysis
Unnamed Item
Unnamed Item
Unnamed Item

This page was built for publication: Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs