Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
From MaRDI portal
Publication:929296
DOI10.1007/s00224-007-9089-3zbMath1148.68041OpenAlexW2076461672MaRDI QIDQ929296
Stefan Richter, Daniel Mölle, Peter Rossmanith
Publication date: 17 June 2008
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-007-9089-3
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (27)
Unnamed Item ⋮ Parameterized Power Vertex Cover ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ On the parameterized complexity of dynamic problems ⋮ The connected vertex cover problem in \(k\)-regular graphs ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Unnamed Item ⋮ An efficient heuristic algorithm for solving connected vertex cover problem ⋮ Connected Vertex Covers in Dense Graphs ⋮ Complexity and algorithms for the connected vertex cover problem in 4-regular graphs ⋮ Parameterized Complexity of Multi-Node Hubs ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ FPT algorithms for connected feedback vertex set ⋮ Connected vertex covers in dense graphs ⋮ Unnamed Item ⋮ Enumerate and Measure: Improving Parameter Budget Management ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ Parameterized algorithm for eternal vertex cover ⋮ The union of minimal hitting sets: parameterized combinatorial bounds and counting ⋮ Parameterized complexity of multi-node hubs ⋮ Revising Johnson's table for the 21st century ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
Cites Work
- Unnamed Item
- Unnamed Item
- An improved fixed-parameter algorithm for vertex cover
- Refined memorization for vertex cover
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Vertex Cover: Further Observations and Further Improvements
- Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants
- On efficient fixed-parameter algorithms for weighted vertex cover
- Algorithms and Data Structures
- A Faster Algorithm for the Steiner Tree Problem
- The steiner problem in graphs
This page was built for publication: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover