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

DOI10.1016/J.TCS.2011.12.065zbMATH Open1237.68089OpenAlexW2157200475MaRDI QIDQ418003FDOQ418003

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

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

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

zbMATH Keywords

matchingbipartite graphblockerNP-completestable setstructural analysis problemtripartite graph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Matching theory
• Blockers and transversals
• Matrices and matroids for systems analysis
• On the NP-completeness of the perfect matching free subgraph problem

Cited In (7)

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

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)