Fixed-Parameter Algorithms for Cluster Vertex Deletion

DOI10.1007/978-3-540-78773-0_61MaRDI QIDQ5458573zbMATH OpenOpenAlexFDO

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

Publication date 15 April 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-78773-0_61

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Fixed-parameter algorithms for cluster vertex deletion
• A tight approximation algorithm for the cluster vertex deletion problem
• A fast branching algorithm for cluster vertex deletion
• A fast branching algorithm for cluster vertex deletion
• Faster parameterized algorithm for cluster vertex deletion

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A More Effective Linear Kernelization for Cluster Editing
• Aggregating inconsistent information
• Applying Modular Decomposition to Parameterized Bicluster Editing
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Correlation clustering with a fixed number of clusters
• Efficient Parameterized Preprocessing for Cluster Editing
• Finding odd cycle transversals.
• Going Weighted: Parameterized Algorithms for Cluster Editing
• Graph-modeled data clustering: Exact algorithms for clique generation
• Improved Parameterized Upper Bounds for Vertex Cover
• Kernelization Algorithms for d-Hitting Set Problems
• Kernels: Annotated, Proper and Induced
• Parameterized Algorithms for Hitting Set: The Weighted Case
• The Cluster Editing Problem: Implementations and Experiments
• The disjoint cliques problem
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(13)

• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Fixed-parameter algorithms for cluster vertex deletion
• Improved Algorithms for Bicluster Editing
• Bounded-degree techniques accelerate some parameterized graph algorithms
• Faster parameterized algorithm for cluster vertex deletion
• Pareto complexity of two-parameter FPT problems: a case study for partial vertex cover
• Fixed-parameter enumerability of cluster editing and related problems
• Cluster vertex deletion: a parameterization between vertex cover and clique-width
• Separator-based data reduction for signed graph balancing
• Kernelization through Tidying
• Iterative Compression and Exact Algorithms
• Fixed-parameter tractability results for feedback set problems in tournaments
• Iterative compression and exact algorithms

This page was built for publication: Fixed-Parameter Algorithms for Cluster Vertex Deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458573)