A polynomial algorithm for the extendability problem in bipartite graphs

DOI10.1016/S0020-0190(97)00177-4MaRDI QIDQ293170zbMATH OpenOpenAlexFDO

Authors J. Lakhal, L. Litzler

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019097001774?np=y

zbMATH Keywords

graph theoryconnectivityperfect matchingextendability

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 2197893
• Construction for bicritical graphs and \(k\)-extendable bipartite graphs
• The matching extension problem in general graphs is co-NP-complete
• scientific article; zbMATH DE number 4066957
• Matching extension and minimum degree

Cites work

• scientific article; zbMATH DE number 4066957 (Why is no real title available?)
• scientific article; zbMATH DE number 3783030 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• A characterization of independent domination critical graphs with a cutvertex
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Matching theory
• Matrix multiplication via arithmetic progressions
• On n-extendable graphs
• Persistency in maximum cardinality bipartite matchings

Cited in

(13)

• scientific article; zbMATH DE number 4199961 (Why is no real title available?)
• 2-extendability of toroidal polyhexes and Klein-bottle polyhexes
• scientific article; zbMATH DE number 27746 (Why is no real title available?)
• Construction for bicritical graphs and \(k\)-extendable bipartite graphs
• Matching theory and Barnette's conjecture
• Extension complexity of stable set polytopes of bipartite graphs
• scientific article; zbMATH DE number 2197893 (Why is no real title available?)
• scientific article; zbMATH DE number 3913665 (Why is no real title available?)
• A polynomial algorithm for b-matchings: An alternative approach
• Extendability and criticality in matching theory
• The matching extension problem in general graphs is co-NP-complete
• Perfect matchings and extended polymatroid
• Surface Embedding of Non-Bipartite $k$-Extendable Graphs

This page was built for publication: A polynomial algorithm for the extendability problem in bipartite graphs

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