A polynomial algorithm for the extendability problem in bipartite graphs

DOI10.1016/S0020-0190(97)00177-4zbMath1339.05397OpenAlexW1969953447MaRDI QIDQ293170

L. Litzler, J. Lakhal

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 theoryconnectivityextendabilityperfect matching

Mathematics Subject Classification ID

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

Related Items (6)

Extendability and criticality in matching theory ⋮ The matching extension problem in general graphs is co-NP-complete ⋮ Construction for bicritical graphs and \(k\)-extendable bipartite graphs ⋮ 2-extendability of toroidal polyhexes and Klein-bottle polyhexes ⋮ Matching theory and Barnette's conjecture ⋮ Surface Embedding of Non-Bipartite $k$-Extendable Graphs

Cites Work

• Matrix multiplication via arithmetic progressions
• Matching theory
• On n-extendable graphs
• Persistency in maximum cardinality bipartite matchings
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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