A tight approximation algorithm for the cluster vertex deletion problem
From MaRDI portal
Publication:5918432
DOI10.1007/978-3-030-73879-2_24zbMath1482.90176arXiv2007.08057OpenAlexW3162862852MaRDI QIDQ5918432
Matthew Drescher, Manuel Aprile, Tony Huynh, Samuel Fiorini
Publication date: 21 December 2021
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.08057
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (5)
A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ A tight approximation algorithm for the cluster vertex deletion problem
Cites Work
- Unnamed Item
- A fast branching algorithm for cluster vertex deletion
- Analysis of complex network performance and heuristic node removal strategies
- Approximate association via dissociation
- Fixed-parameter algorithms for cluster vertex deletion
- Decomposition by clique separators
- Polyhedral properties of the induced cluster subgraphs
- Improved approximation algorithms for hitting 3-vertex paths
- Faster parameterized algorithm for pumpkin vertex deletion set
- An Approximation Algorithm for Feedback Vertex Sets in Tournaments
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A 7/3-Approximation for Feedback Vertex Sets in Tournaments
- Subquadratic Kernels for Implicit 3-H <scp>itting</scp> S <scp>et</scp> and 3-S <scp>et</scp> P <scp>acking</scp> Problems
- 2-Approximating Feedback Vertex Set in Tournaments
- No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
- Exact Algorithms via Monotone Local Search
- A tight approximation algorithm for the cluster vertex deletion problem
- Graph fragmentation problem: analysis and synthesis
This page was built for publication: A tight approximation algorithm for the cluster vertex deletion problem