On efficient fixed-parameter algorithms for weighted vertex cover

DOI10.1016/S0196-6774(03)00005-1zbMath1046.68058OpenAlexW2030295282MaRDI QIDQ4420418

Rolf Niedermeier, Peter Rossmanith

Publication date: 17 August 2003

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0196-6774(03)00005-1

zbMATH Keywords

dynamic programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Refined memorization for vertex cover ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Multi-start iterated tabu search for the minimum weight vertex cover problem ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ Parameterized Power Vertex Cover ⋮ A multivariate framework for weighted FPT algorithms ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ On the approximability and hardness of minimum topic connected overlay and its special instances ⋮ Extended dynamic subgraph statistics using \(h\)-index parameterized data structures ⋮ Confronting intractability via parameters ⋮ Enumerate and expand: Improved algorithms for connected vertex cover and tree cover ⋮ A note on the complexity of minimum dominating set ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Heuristics for automated knowledge source integration and service composition ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ Parameterized algorithms for \(d\)-hitting set: the weighted case ⋮ Improved upper bounds for vertex cover ⋮ Fixed-parameter algorithms for cluster vertex deletion ⋮ Counting the number of vertex covers in a trapezoid graph ⋮ Fixed-parameter tractability and data reduction for multicut in trees ⋮ On two techniques of combining branching and treewidth ⋮ On parameterized exponential time complexity ⋮ A refined search tree technique for dominating set on planar graphs