Parameterized complexity of Vertex Cover variants

DOI10.1007/s00224-007-1309-3zbMath1147.68607OpenAlexW2156896570MaRDI QIDQ2464318

Sebastian Wernicke, Jiong Guo, Rolf Niedermeier

Publication date: 19 December 2007

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-1309-3

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (36)

Parameterized Power Vertex Cover ⋮ Parameterized Complexity for Domination Problems on Degenerate Graphs ⋮ Parameterized algorithms for graph partitioning problems ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Capacitated Domination and Covering: A Parameterized Perspective ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ Disentangling the computational complexity of network untangling ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Subexponential algorithms for partial cover problems ⋮ FPT approximation and subexponential algorithms for covering few or many edges ⋮ Vertex cover problem parameterized above and below tight bounds ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ Maximizing coverage while ensuring fairness: a tale of conflicting objectives ⋮ On the \(k\)-edge-incident subgraph problem and its variants ⋮ An improved parameterized algorithm for the independent feedback vertex set problem ⋮ Exact algorithms for problems related to the densest \(k\)-set problem ⋮ Connected Vertex Covers in Dense Graphs ⋮ Implicit branching and parameterized partial cover problems ⋮ Genomic Scaffold Filling: A Progress Report ⋮ Improved Approximations for Hard Optimization Problems via Problem Instance Classification ⋮ Incremental problems in the parameterized complexity setting ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ Connected vertex covers in dense graphs ⋮ Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover ⋮ Enumerate and Measure: Improving Parameter Budget Management ⋮ Parameterized algorithms for finding highly connected solution ⋮ Efficient algorithms for network localization using cores of underlying graphs ⋮ Parameterized algorithm for eternal vertex cover ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Partial vertex cover on graphs of bounded degeneracy ⋮ Parameterized algorithms for finding highly connected solution ⋮ Combinatorial voter control in elections ⋮ Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs

This page was built for publication: Parameterized complexity of Vertex Cover variants