On the parameterized vertex cover problem for graphs with perfect matching

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

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

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-completevertex coverparameterized algorithmiterative compression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved fixed-parameter algorithm for vertex cover
• On approximating minimum vertex cover for graphs with perfect matching
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• Finding odd cycle transversals.
• Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
• Parameterizing above or below guaranteed values
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• On the existence of subexponential parameterized algorithms
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex Cover: Further Observations and Further Improvements
• On Multiway Cut Parameterized above Lower Bounds
• Paths, Flowers and Vertex Cover
• Parameterizing MAX SNP Problems Above Guaranteed Values
• Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• König Deletion Sets and Vertex Covers above the Matching Size
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• Improved Parameterized Upper Bounds for Vertex Cover

This page was built for publication: On the parameterized vertex cover problem for graphs with perfect matching