Algorithms and Data Structures

DOI10.1007/11534273zbMath1161.68669OpenAlexW3010016474MaRDI QIDQ5394236

Rolf Niedermeier, Jiong Guo, Sebastian Wernicke

Publication date: 25 October 2006

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11534273

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Improved Upper Bounds for Partial Vertex Cover ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ Computing optimal Steiner trees in polynomial space ⋮ On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ A Purely Democratic Characterization of W[1] ⋮ The connected vertex cover problem in \(k\)-regular graphs ⋮ Complexity and Approximation Results for the Connected Vertex Cover Problem ⋮ A parameterized approximation scheme for generalized partial vertex cover ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ Matroid-constrained vertex cover ⋮ Circumventing connectivity for kernelization ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ Enumerate and expand: Improved algorithms for connected vertex cover and tree cover ⋮ Complexity and algorithms for the connected vertex cover problem in 4-regular graphs ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Definition and algorithms for reliable Steiner tree problem ⋮ Parameterized Complexity of Multi-Node Hubs ⋮ Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ On problems without polynomial kernels ⋮ Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs ⋮ Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover ⋮ Parameterized complexity of multi-node hubs ⋮ Unnamed Item ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints