On the parameterized vertex cover problem for graphs with perfect matching

DOI10.1007/s11432-013-4845-2zbMath1343.68122MaRDI QIDQ893740

Jianxin Wang, Wenjun Li, Jian'er Chen, Shao-hua Li

Publication date: 20 November 2015

Published in: Science China. Information Sciences (Search for Journal in Brave)

Full work available at URL: http://engine.scichina.com/doi/10.1007/s11432-013-4845-2

zbMATH Keywords

NP-complete; vertex cover; parameterized algorithm; iterative compression

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Uses Software

• DIMACS