An improved fixed-parameter algorithm for vertex cover

DOI10.1016/S0020-0190(97)00213-5zbMATH Open1337.05095OpenAlexW1972577597MaRDI QIDQ293227FDOQ293227

Authors: 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

Recommendations

• Improved Parameterized Upper Bounds for Vertex Cover
• Publication:4944990
• Improved upper bounds for vertex cover
• scientific article; zbMATH DE number 1304341
• A note on vertex cover in graphs with maximum degree 3

zbMATH Keywords

algorithmsfixed-parameter tractabilityvertex cover

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Title not available (Why is that?)
• 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^ * $

Cited In (57)

• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• Efficient algorithms for the max \(k\)-vertex cover problem
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• Solving larger maximum clique problems using parallel quantum annealing
• Fixed-parameter evolutionary algorithms and the vertex cover problem
• Refined memorization for vertex cover
• Above guarantee parameterization for vertex cover on graphs with maximum degree 4
• An efficient fixed-parameter algorithm for 3-hitting set
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• A kernel of order \(2k-c\log k\) for vertex cover
• Parameterized and Exact Computation
• The Impact of Parameterized Complexity to Interdisciplinary Problem Solving
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• A fixed-parameter-tractable algorithm for set packing
• Graph-Theoretic Concepts in Computer Science
• Title not available (Why is that?)
• On efficient fixed-parameter algorithms for weighted vertex cover
• Improved upper bounds for vertex cover
• A general method to speed up fixed-parameter-tractable algorithms
• Solving large FPT problems on coarse-grained parallel machines
• On the parameterized vertex cover problem for graphs with perfect matching
• Rank vertex cover as a natural problem for algebraic compression
• A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEM
• Pareto complexity of two-parameter FPT problems: a case study for partial vertex cover
• Improved Parameterized Upper Bounds for Vertex Cover
• Title not available (Why is that?)
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• Title not available (Why is that?)
• What Is Known About Vertex Cover Kernelization?
• Confronting intractability via parameters
• Maximum minimal vertex cover parameterized by vertex cover
• A note on the complexity of minimum dominating set
• Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP
• Parameterized computation and complexity: a new approach dealing with NP-hardness
• On parameterized exponential time complexity
• Parameterized algorithm for eternal vertex cover
• On the existence of subexponential parameterized algorithms
• Reachability problems in interval-constrained and cardinality-constrained graphs
• Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}
• Generating Faster Algorithms for d-Path Vertex Cover
• An \(O^\ast ( 2 . 61 9^k )\) algorithm for 4-path vertex cover
• Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
• Intuitive Algorithms and t-Vertex Cover
• An efficient exact algorithm for constraint bipartite vertex cover
• Title not available (Why is that?)
• A kernel of order \(2k - c\) for Vertex Cover
• Why is maximum clique often easy in practice?
• Vertex cover, dominating set and my encounters with parameterized complexity and Mike Fellows
• Maximum minimal vertex cover parameterized by vertex cover
• Improved exact algorithms for MAX-SAT
• Title not available (Why is that?)
• Parameterized measure \& conquer for problems with no small kernels
• A note on vertex cover in graphs with maximum degree 3
• Deterministic parameterized connected vertex cover
• A multivariate framework for weighted FPT algorithms
• The complexity of irredundant sets parameterized by size
• Title not available (Why is that?)

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

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