A fast branching algorithm for cluster vertex deletion
From MaRDI portal
Publication:255285
DOI10.1007/S00224-015-9631-7zbMath1336.68192OpenAlexW2001878420WikidataQ59473167 ScholiaQ59473167MaRDI QIDQ255285
Anudhyan Boral, Marcin Pilipczuk, Tomasz Kociumaka, Marek Cygan
Publication date: 9 March 2016
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-015-9631-7
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (31)
Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ \(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 ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ Faster parameterized algorithms for two vertex deletion problems ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters ⋮ Approximate association via dissociation ⋮ Parameterized algorithms for the happy set problem ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization ⋮ Faster parameterized algorithm for cluster vertex deletion ⋮ On the \(d\)-claw vertex deletion problem ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Minimum eccentricity shortest path problem with respect to structural parameters ⋮ Structural parameterizations of budgeted graph coloring ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Minimum eccentricity shortest path problem with respect to structural parameters ⋮ Structural parameterizations of budgeted graph coloring ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels ⋮ On independent cliques and linear complementarity problems
Cites Work
- A \(2k\) kernel for the cluster editing problem
- Exact exponential algorithms.
- Correlation clustering
- Finding odd cycle transversals.
- Cluster editing with locally bounded modifications
- A top-down approach to search-trees: Improved algorithmics for 3-hitting set
- Fixed-parameter algorithms for cluster vertex deletion
- A kernelization algorithm for \(d\)-hitting set
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Automated generation of search tree algorithms for hard graphs modification problems
- A golden ratio parameterized algorithm for cluster editing
- Applying modular decomposition to parameterized cluster editing problems
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- Clustering with qualitative information
- Linear time algorithms for graph search and connectivity determination on complement graphs.
- Kernels: Annotated, Proper and Induced
- Cluster Editing
- Aggregating inconsistent information
This page was built for publication: A fast branching algorithm for cluster vertex deletion
