A tight approximation algorithm for the cluster vertex deletion problem
From MaRDI portal
(Redirected from Publication:5925651)
A tight approximation algorithm for the cluster vertex deletion problem (scientific article; zbMATH DE number 7662926)
A tight approximation algorithm for the cluster vertex deletion problem (scientific article; zbMATH DE number 7662926)
Recommendations
Cites work
- 2-Approximating Feedback Vertex Set in Tournaments
- A 7/3-approximation for feedback vertex sets in tournaments
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A fast branching algorithm for cluster vertex deletion
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A tight approximation algorithm for the cluster vertex deletion problem
- An approximation algorithm for feedback vertex sets in tournaments
- Analysis of complex network performance and heuristic node removal strategies
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Decomposition by clique separators
- Extended formulations for matroid polytopes through randomized protocols
- Extension complexity of stable set polytopes of bipartite graphs
- Extension complexity, MSO logic, and treewidth
- Fixed-parameter algorithms for cluster vertex deletion
- Graph fragmentation problem: analysis and synthesis
- scientific article; zbMATH DE number 1234104 (Why is no real title available?)
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- Inapproximability of combinatorial problems via small LPs and SDPs
- Integer Programming
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- Polyhedral properties of the induced cluster subgraphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems
- The probabilistic method
- Vertex deletion problems on chordal graphs
Cited in
(19)- Faster parameterized algorithm for cluster vertex deletion
- Approximation and tidying -- a problem kernel for s-plex cluster vertex deletion
- On the d-claw vertex deletion problem
- Kernelization through Tidying
- Fixed-Parameter Algorithms for Cluster Vertex Deletion
- A tight approximation algorithm for the cluster vertex deletion problem
- \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs
- On the parameterized complexity of s-club cluster deletion problems
- Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
- Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
- Parameterized algorithms for locating-dominating sets
- Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
- Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
- Graph clustering problems under the Lens of parameterized local search
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Graph clustering problems under the Lens of parameterized local search
- Efficient parameterized approximation
- A linear-delay algorithm for enumerating strongly-connected induced subgraphs based on SSD set system
This page was built for publication: A tight approximation algorithm for the cluster vertex deletion problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5925651)
