Connected matchings in chordal bipartite graphs

DOI10.1016/J.DISOPT.2014.06.003zbMATH Open1308.90149OpenAlexW2084866560MaRDI QIDQ2339830FDOQ2339830

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

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

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)

Cites Work

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

Cited In (7)

• The bipartite margin shop and maximum red matchings free of blue-red alternating cycles
• Multitasking capacity: hardness results and improved constructions
• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
• Polyhedral approach to weighted connected matchings in general graphs
• Disconnected matchings
• Disconnected matchings
• Title not available (Why is that?)

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)