Excluded t-factors in bipartite graphs: a unified framework for nonbipartite matchings and restricted 2-matchings

DOI10.1007/978-3-319-59250-3_35MaRDI QIDQ2401181zbMATH OpenOpenAlexFDO

Authors Kenjiro Takazawa

Publication date 31 August 2017

Full work available at URL https://arxiv.org/abs/1708.00582

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: We propose a framework for optimal $t$-matchings excluding the prescribed $t$-factors in bipartite graphs. The proposed framework is a generalization of the nonbipartite matching problem and includes several problems, such as the triangle-free $2$-matching, square-free $2$-matching, even factor, and arborescence problems. In this paper, we demonstrate a unified understanding of these problems by commonly extending previous important results. We solve our problem under a reasonable assumption, which is sufficiently broad to include the specific problems listed above. We first present a min-max theorem and a combinatorial algorithm for the unweighted version. We then provide a linear programming formulation with dual integrality and a primal-dual algorithm for the weighted version. A key ingredient of the proposed algorithm is a technique to shrink forbidden structures, which corresponds to the techniques of shrinking odd cycles, triangles, squares, and directed cycles in Edmonds' blossom algorithm, a triangle-free $2$-matching algorithm, a square-free $2$-matching algorithm, and an arborescence algorithm, respectively.

Recommendations

• Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids
• Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
• A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs
• Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs
• A weighted \(K_{t,t}\)-free \(t\)-factor algorithm for bipartite graphs

Cited in

(9)

• Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
• A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges
• Complexity of packing common bases in matroids
• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
• A weighted \(K_{t,t}\)-free \(t\)-factor algorithm for bipartite graphs
• A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs
• scientific article; zbMATH DE number 7378329 (Why is no real title available?)
• 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

This page was built for publication: Excluded \(t\)-factors in bipartite graphs: a unified framework for nonbipartite matchings and restricted 2-matchings

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