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

DOI10.1016/j.tcs.2011.12.065zbMath1237.68089OpenAlexW2157200475MaRDI QIDQ418003

Christophe Picouleau, Mathieu Lacroix, Sébastien Martin, Ali Ridha 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 graphmatchingstable setNP-completetripartite graphblockerstructural analysis problem

Mathematics Subject Classification ID

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

Related Items (7)

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

Cites Work

• Unnamed Item
• On the NP-completeness of the perfect matching free subgraph problem
• Blockers and transversals
• Matching theory
• Matrices and matroids for systems analysis

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