On the parameterized vertex cover problem for graphs with perfect matching
type: Item
instance of: scholarly article
title: On the parameterized vertex cover problem for graphs with perfect matching
zbMATH Open document ID: 1343.68122
author: Jianxin Wang
author: Wen-Jun Li
author: Shao-Hua Li
author: Jianer Chen
publication date: 2015-11-20T00:00:00Z
full work available at URL: s11432-013-4845-2
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6512376
zbMATH Keywords: NP-complete
zbMATH Keywords: parameterized algorithm
zbMATH Keywords: vertex cover
zbMATH Keywords: iterative compression
describes a project that uses: DIMACS
MaRDI profile type: Publication
OpenAlex ID: W2022122931
cites work: Q4198056
cites work: An improved fixed-parameter algorithm for vertex cover
cites work: Vertex cover: Further observations and further improvements
cites work: Q4850549
cites work: Q4251072
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Improved Parameterized Upper Bounds for Vertex Cover
cites work: On the existence of subexponential parameterized algorithms
cites work: Local search with edge weighting and configuration checking heuristics for minimum vertex cover
cites work: Q4714131
cites work: Random constraint satisfaction: easy generation of hard (satisfiable) instances
cites work: On approximating minimum vertex cover for graphs with perfect matching
cites work: Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Parameterizing MAX SNP Problems Above Guaranteed Values
cites work: Parameterizing above or below guaranteed values
cites work: Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
cites work: The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
cites work: Finding odd cycle transversals.
cites work: Independence numbers of graphs - an extension of the Koenig-Egervary theorem
cites work: A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
cites work: Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
cites work: König Deletion Sets and Vertex Covers above the Matching Size
cites work: Paths, Flowers and Vertex Cover
cites work: On Multiway Cut Parameterized above Lower Bounds
cites work: LP can be a cure for parameterized problems
DOI: 10.1007/S11432-013-4845-2
published in: Science China Information Sciences
description: scientific article; zbMATH DE number 6512376