Connected matchings in chordal bipartite graphs

DOI10.1016/J.DISOPT.2014.06.003MaRDI QIDQ2339830zbMATH OpenOpenAlexFDO

Authors Adam S. Jobson, André E. Kézdy, Susan C. White

Publication date 9 April 2015

Published in Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

chordal bipartite graphsHadwiger numberconnected matchingbipartite margin shop problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Recommendations

• scientific article; zbMATH DE number 1953189
• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Induced matchings
• A min-max property of chordal bipartite graphs with applications

Cites work

• scientific article; zbMATH DE number 1953189 (Why is no real title available?)
• A notion of cross-perfect bipartite graphs
• Algorithmic graph theory and perfect graphs
• Alternating cycle-free matchings
• Approximating the maximum clique minor and some subgraph homeomorphism problems
• Finding Large Clique Minors is Hard
• Maximum induced matchings for chordal graphs in linear time
• Node-Deletion Problems on Bipartite Graphs
• On a special case of Hadwiger's conjecture
• On the complexity of approximating the Hadwiger number
• The bipartite margin shop and maximum red matchings free of blue-red alternating cycles

Cited in

(7)

• The bipartite margin shop and maximum red matchings free of blue-red alternating cycles
• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
• scientific article; zbMATH DE number 1953189 (Why is no real title available?)
• Disconnected matchings
• Disconnected matchings
• Multitasking capacity: hardness results and improved constructions
• Polyhedral approach to weighted connected matchings in general graphs

This page was built for publication: Connected matchings in chordal bipartite graphs

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