Fixed-parameter algorithms for cluster vertex deletion

DOI10.1007/s00224-008-9150-xzbMath1205.68263OpenAlexW3101793140MaRDI QIDQ987386

Falk Hüffner, Rolf Niedermeier, Christian Komusiewicz, Hannes Moser

Publication date: 13 August 2010

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

Full work available at URL: https://doi.org/10.1007/s00224-008-9150-x

zbMATH Keywords

clusteringgraph algorithmsNP-hard problemsparameterized complexityiterative compression

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (46)

On Making Directed Graphs Transitive ⋮ Reducing rank of the adjacency matrix by graph modification ⋮ Reducing Rank of the Adjacency Matrix by Graph Modification ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ The maximum independent union of cliques problem: complexity and exact approaches ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ Fixed-parameter tractable distances to sparse graph classes ⋮ Parameterized algorithms for min-max 2-cluster editing ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ A golden ratio parameterized algorithm for cluster editing ⋮ An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ A polynomial kernel for 3-leaf power deletion ⋮ Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ Improved approximation algorithms for hitting 3-vertex paths ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ On making directed graphs transitive ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ Algorithms for 2-club cluster deletion problems using automated generation of branching rules ⋮ Even faster parameterized cluster deletion and cluster editing ⋮ Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion ⋮ Recognizing map graphs of bounded treewidth ⋮ Asymptotic bounds for clustering problems in random graphs ⋮ An FPT algorithm for the vertex cover \(P_4\) problem ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space ⋮ Confronting intractability via parameters ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ A fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ Towards optimal and expressive kernelization for \(d\)-hitting set ⋮ Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions ⋮ Approximate association via dissociation ⋮ An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ The firefighter problem: further steps in understanding its complexity ⋮ Constant thresholds can make target set selection tractable ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Unnamed Item ⋮ Faster parameterized algorithm for cluster vertex deletion ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Alternative Parameterizations for Cluster Editing ⋮ A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics ⋮ A fast branching algorithm for cluster vertex deletion ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Graph-modeled data clustering: Exact algorithms for clique generation
• Parameterized algorithms for feedback set problems and their duals in tournaments
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• A general method to speed up fixed-parameter-tractable algorithms
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Applying modular decomposition to parameterized cluster editing problems
• An Approximation Algorithm for Feedback Vertex Sets in Tournaments
• Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
• Parameterized Algorithms for Hitting Set: The Weighted Case
• The Cluster Editing Problem: Implementations and Experiments
• Kernels: Annotated, Proper and Induced
• Iterative Compression and Exact Algorithms
• Kernelization Algorithms for d-Hitting Set Problems
• A More Effective Linear Kernelization for Cluster Editing
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• The disjoint cliques problem
• On efficient fixed-parameter algorithms for weighted vertex cover
• Faster Scaling Algorithms for Network Problems
• On the hardness of approximating minimization problems
• Deterministic Algorithms for Rank Aggregation and Other Ranking and Clustering Problems
• Efficient Parameterized Preprocessing for Cluster Editing
• Going Weighted: Parameterized Algorithms for Cluster Editing
• Improved Parameterized Upper Bounds for Vertex Cover
• Aggregating inconsistent information

This page was built for publication: Fixed-parameter algorithms for cluster vertex deletion