An algorithm for finding a maximum \(t\)-matching excluding complete partite subgraphs

DOI10.1016/j.disopt.2012.02.003zbMath1246.05150OpenAlexW2046239121MaRDI QIDQ448969

Yusuke Kobayashi, Xin Yin

Publication date: 11 September 2012

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

Full work available at URL: https://doi.org/10.1016/j.disopt.2012.02.003

zbMATH Keywords

polynomial-time algorithmshrinkingb-matchingcomplete partite graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids ⋮ Decomposition theorems for square-free 2-matchings in bipartite graphs ⋮ A proof of Cunningham's conjecture on restricted subgraphs and jump systems ⋮ Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs

Cites Work

• A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs
• Combinatorial algorithms for matchings, even factors and square-free 2-factors
• A matching problem with side conditions
• Restricted \(t\)-matchings in bipartite graphs
• Finding maximum square-free 2-matchings in bipartite graphs
• Even factors, jump systems, and discrete convexity
• Augmenting Undirected Node-Connectivity by One
• A Weighted k_{t, t}-Free t-Factor Algorithm for Bipartite Graphs
• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• Restricted b-Matchings in Degree-Bounded Graphs
• Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)

This page was built for publication: An algorithm for finding a maximum \(t\)-matching excluding complete partite subgraphs