A polynomial algorithm for the extendability problem in bipartite graphs

DOI10.1016/S0020-0190(97)00177-4zbMATH Open1339.05397OpenAlexW1969953447MaRDI QIDQ293170FDOQ293170

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

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

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)

Cites Work

• Matching theory
• Persistency in maximum cardinality bipartite matchings
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Matrix multiplication via arithmetic progressions
• On n-extendable graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A characterization of independent domination critical graphs with a cutvertex
• Title not available (Why is that?)

Cited In (13)

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

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)