On the parameterized vertex cover problem for graphs with perfect matching

DOI10.1007/S11432-013-4845-2MaRDI QIDQ893740zbMATH OpenOpenAlexFDO

Authors Jianxin Wang, Wen-Jun Li, Shao-Hua Li, Jianer 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

iterative compressionNP-completeparameterized algorithmvertex cover

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

Recommendations

• Computing and Combinatorics
• scientific article; zbMATH DE number 2080241
• On approximating minimum vertex cover for graphs with perfect matching
• The complexity of König subgraph problems and above-guarantee vertex cover
• Paths, flowers and vertex cover

Cites work

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

Cited in

(7)

• Perfectly matched sets in graphs: parameterized and exact computation
• Maintaining a large matching and a small vertex cover
• Paths, flowers and vertex cover
• Graph Layout Problems Parameterized by Vertex Cover
• scientific article; zbMATH DE number 2080241 (Why is no real title available?)
• Computing and Combinatorics
• On approximating minimum vertex cover for graphs with perfect matching

Describes a project that uses

Uses Software

• DIMACS

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

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