Faster parameterized algorithm for cluster vertex deletion

DOI10.1007/s00224-020-10005-wOpenAlexW3094363627MaRDI QIDQ2035480

Dekel Tsur

Publication date: 24 June 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1901.07609

zbMATH Keywords

graph algorithmsparameterized complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (10)

On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ On conflict-free spanning tree: algorithms and complexity ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Algorithms for 2-club cluster deletion problems using automated generation of branching rules ⋮ On the parameterized complexity of s-club cluster deletion problems ⋮ On the \(d\)-claw vertex deletion problem ⋮ Faster parameterized algorithms for two vertex deletion problems ⋮ On the \(d\)-claw vertex deletion problem

Cites Work

• A fast branching algorithm for cluster vertex deletion
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• Correlation clustering
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• A faster FPT algorithm for 3-path vertex cover
• Fixed-parameter algorithms for cluster vertex deletion
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• Automated generation of search tree algorithms for hard graphs modification problems
• Iterative compression and exact algorithms
• Parameterized algorithm for 3-path vertex cover
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
• Exact Algorithms via Monotone Local Search
• Parameterized Algorithms

This page was built for publication: Faster parameterized algorithm for cluster vertex deletion