Parameterized approximation algorithms for weighted vertex cover

DOI10.1016/J.TCS.2024.114870MaRDI QIDQ6639732zbMATH OpenFDO

Authors Soumen Mandal, Pranabendu Misra, Ashutosh Rai, Saket Saurabh

Publication date 18 November 2024

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

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114870

zbMATH Keywords

approximation algorithmsparameterized algorithmsparameterized approximationweighted vertex cover

Mathematics Subject Classification ID

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

Recommendations

• On efficient fixed-parameter algorithms for weighted vertex cover
• scientific article; zbMATH DE number 2080245
• Combining Two Worlds: Parameterised Approximation for Vertex Cover
• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• A note on max k-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation

Cites work

• A multivariate framework for weighted FPT algorithms
• 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
• Branching and Treewidth Based Exact Algorithms
• Directed flow-augmentation
• Improved algorithms for feedback vertex set problems
• On efficient fixed-parameter algorithms for weighted vertex cover
• Parameterized algorithms
• Parameterized approximation via fidelity preserving transformations
• Parameterized complexity of weighted multicut in trees
• Reducibility among combinatorial problems
• Towards a proof of the 2-to-1 games conjecture?
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex packings: Structural properties and algorithms

Cited in

(4)

• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
• On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
• A note on max k-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation
• Temporal dominating set and temporal vertex cover under the lens of degree restrictions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6639732)