Parameterized approximation algorithms for weighted vertex cover
DOI10.1016/J.TCS.2024.114870MaRDI QIDQ6639732FDOQ6639732
Authors: Soumen Mandal, Pranabendu Misra, Ashutosh Rai, Saket Saurabh 
Publication date: 18 November 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
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
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Reducibility among combinatorial problems
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Parameterized algorithms
- Improved algorithms for feedback vertex set problems
- Vertex packings: Structural properties and algorithms
- On efficient fixed-parameter algorithms for weighted vertex cover
- Branching and Treewidth Based Exact 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
- Parameterized complexity of weighted multicut in trees
- Parameterized approximation via fidelity preserving transformations
- A multivariate framework for weighted FPT algorithms
- Towards a proof of the 2-to-1 games conjecture?
- Directed flow-augmentation
Cited In (2)
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)
