On the NP-completeness of the perfect matching free subgraph problem

DOI10.1016/J.TCS.2011.12.065MaRDI QIDQ418003zbMATH OpenOpenAlexFDO

Authors Mathieu Lacroix, Sébastien Martin, Christophe Picouleau, A. R. Mahjoub

Publication date 14 May 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.12.065

zbMATH Keywords

bipartite graphblockermatchingNP-completestable setstructural analysis problemtripartite graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Partitioning to three matchings of given size is NP-complete for bipartite graphs
• On complexity of special maximum matchings constructing
• On the completeness of a generalized matching problem
• Certain NP-complete matching problems
• Perfectly matchable subgraph problem on a bipartite graph

Cites work

• Blockers and transversals
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Matching theory
• Matrices and matroids for systems analysis
• On the NP-completeness of the perfect matching free subgraph problem

Cited in

(7)

• Strong matching preclusion number of graphs
• Matching preclusion number of graphs
• Fractional matching preclusion number of graphs and the perfect matching polytope
• On the NP-completeness of the perfect matching free subgraph problem
• How to Secure Matchings Against Edge Failures
• How to Secure Matchings against Edge Failures
• On anti-Kekulé and s-restricted matching preclusion problems

This page was built for publication: On the NP-completeness of the perfect matching free subgraph problem

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