The matching extension problem in general graphs is co-NP-complete

DOI10.1007/S10878-017-0226-XMaRDI QIDQ1743490zbMATH OpenOpenAlexFDO

Authors Jan Hackfeld, Arie M. C. A. Koster

Publication date 13 April 2018

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-017-0226-x

zbMATH Keywords

complexityextendabilityperfect matching

Mathematics Subject Classification ID

Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Generalization of matching extensions in graphs
• Extending matchings in graphs: A survey
• scientific article; zbMATH DE number 1161241
• Generalization of matching extensions in graphs. II.
• scientific article; zbMATH DE number 1563920
• On the complexity of some problems related to graph extensions
• Generalization of matching extensions in graphs. III
• Matchings and matching extensions in graphs
• scientific article; zbMATH DE number 867631
• scientific article; zbMATH DE number 4193713

Cites work

• A polynomial algorithm for the extendability problem in bipartite graphs
• Construction for bicritical graphs and \(k\)-extendable bipartite graphs
• Extending matchings in graphs: A survey
• Paths, Trees, and Flowers
• Recent Progress in Matching Extension
• Reducibility among combinatorial problems

Cited in

(9)

• The distance matching extension in \(K_{1,k}\)-free graphs with high local connectedness
• 1-extendability of independent sets
• Extendability and criticality in matching theory
• A polynomial algorithm for the extendability problem in bipartite graphs
• 1-extendability of independent sets
• The extendability of Cayley graphs generated by transpositions
• On the fractional matching extendability of Cayley graphs of abelian groups
• Matching extendability in Cartesian product of hypercubes and paths
• Extending unlocked matchings in graphs

This page was built for publication: The matching extension problem in general graphs is co-NP-complete

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