An improved fixed-parameter algorithm for vertex cover

DOI10.1016/S0020-0190(97)00213-5zbMath1337.05095OpenAlexW1972577597MaRDI QIDQ293227

R. Balasubramanian, Michael R. Fellows, Venkatesh Raman

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097002135?np=y

zbMATH Keywords

algorithmsvertex coverfixed-parameter tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (31)

Solving large FPT problems on coarse-grained parallel machines ⋮ On the existence of subexponential parameterized algorithms ⋮ Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms ⋮ Improved exact algorithms for MAX-SAT ⋮ Refined memorization for vertex cover ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ The Impact of Parameterized Complexity to Interdisciplinary Problem Solving ⋮ Vertex Cover, Dominating Set and My Encounters with Parameterized Complexity and Mike Fellows ⋮ A multivariate framework for weighted FPT algorithms ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ Reachability problems in interval-constrained and cardinality-constrained graphs ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Confronting intractability via parameters ⋮ Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP ⋮ Enumerate and expand: Improved algorithms for connected vertex cover and tree cover ⋮ The complexity of irredundant sets parameterized by size ⋮ Unnamed Item ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ A note on the complexity of minimum dominating set ⋮ Improved upper bounds for vertex cover ⋮ A fixed-parameter-tractable algorithm for set packing ⋮ A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEM ⋮ On parameterized exponential time complexity ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression ⋮ Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover ⋮ Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ A general method to speed up fixed-parameter-tractable algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• On limited nondeterminism and the complexity of the V-C dimension
• Nondeterminism within $P^ * $
• Fixed-Parameter Tractability and Completeness I: Basic Results

This page was built for publication: An improved fixed-parameter algorithm for vertex cover