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

DOI10.1016/J.DISOPT.2012.02.003MaRDI QIDQ448969zbMATH OpenOpenAlexFDO

Authors 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Recommendations

• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs
• Restricted \(b\)-matchings in degree-bounded graphs
• Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs
• Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs

Cites work

• A matching problem with side conditions
• A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs
• A weighted \(K_{t,t}\)-free \(t\)-factor algorithm for bipartite graphs
• Augmenting undirected node-connectivity by one
• Combinatorial algorithms for matchings, even factors and square-free 2-factors
• Even factors, jump systems, and discrete convexity
• Finding maximum square-free 2-matchings in bipartite graphs
• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• Restricted \(b\)-matchings in degree-bounded graphs
• Restricted \(t\)-matchings in bipartite graphs
• Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)

Cited in

(11)

• A proof of Cunningham's conjecture on restricted subgraphs and jump systems
• Tutte sets in graphs. II: The complexity of finding maximum Tutte sets
• Decomposition theorems for square-free 2-matchings in bipartite graphs
• Restricted \(t\)-matchings in bipartite graphs
• A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs
• Decomposition theorems for square-free 2-matchings in bipartite graphs
• scientific article; zbMATH DE number 6299967 (Why is no real title available?)
• Restricted \(b\)-matchings in degree-bounded graphs
• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids
• An algorithm for matching problems of multi-partite graphs which include one cycle

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

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