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

NP-completevertex coverparameterized algorithmiterative compression

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) 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)

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

• 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?)
• 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.
• 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
• LP can be a cure for parameterized problems
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• 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 MAX SNP Problems Above Guaranteed Values
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parameterizing above or below 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)

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

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)