Parameterized approximation algorithms for weighted vertex cover

DOI10.1016/j.tcs.2024.114870MaRDI QIDQ6639732

Ashutosh Rai, Pranabendu Misra, Soumen Mandal, Saket Saurabh

Publication date: 18 November 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsparameterized algorithmsparameterized approximationweighted vertex cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Improved algorithms for feedback vertex set problems
• Parameterized approximation via fidelity preserving transformations
• A multivariate framework for weighted FPT algorithms
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex packings: Structural properties and algorithms
• On efficient fixed-parameter algorithms for weighted vertex cover
• Reducibility among Combinatorial Problems
• Towards a proof of the 2-to-1 games conjecture?
• Branching and Treewidth Based Exact Algorithms
• Parameterized Algorithms
• Parameterized complexity of weighted multicut in trees
• Directed flow-augmentation

This page was built for publication: Parameterized approximation algorithms for weighted vertex cover