On the parameterized vertex cover problem for graphs with perfect matching
DOI10.1007/S11432-013-4845-2zbMATH Open1343.68122OpenAlexW2022122931MaRDI QIDQ893740FDOQ893740
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Finding odd cycle transversals.
- Parameterizing above or below guaranteed values
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- On multiway cut parameterized above lower bounds
- LP can be a cure for parameterized problems
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Title not available (Why is that?)
- 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
- An improved fixed-parameter algorithm for vertex cover
- Improved Parameterized Upper Bounds for Vertex Cover
- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
- Local search with edge weighting and configuration checking heuristics for minimum vertex cover
- Title not available (Why is that?)
- Vertex cover: Further observations and further improvements
- Paths, flowers and vertex cover
- Title not available (Why is that?)
- Parameterizing MAX SNP Problems Above Guaranteed Values
- On approximating minimum vertex cover for graphs with perfect matching
- Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
- The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
- Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
- König Deletion Sets and Vertex Covers above the Matching Size
Cited In (6)
Uses Software
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)
