Fixed-parameter enumerability of cluster editing and related problems

DOI10.1007/s00224-008-9130-1zbMath1209.68360OpenAlexW2019003450MaRDI QIDQ970105

Peter Damaschke

Publication date: 10 May 2010

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

Full work available at URL: https://doi.org/10.1007/s00224-008-9130-1

zbMATH Keywords

enumeration problemsfixed-parameter tractabilitysoft clusteringcluster graphstrue twins

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (16)

Graph-Based Data Clustering with Overlaps ⋮ Cluster Editing ⋮ On the complexity of multi-parameterized cluster editing ⋮ Cluster editing problem for points on the real line: a polynomial time algorithm ⋮ Parameterized algorithms for min-max 2-cluster editing ⋮ Efficient enumeration of the optimal solutions to the correlation clustering problem ⋮ Even faster parameterized cluster deletion and cluster editing ⋮ Graph-based data clustering with overlaps ⋮ Tight bounds for parameterized complexity of cluster editing with a small number of clusters ⋮ Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions ⋮ A faster algorithm for the cluster editing problem on proper interval graphs ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem ⋮ Generalized Graph Clustering: Recognizing (p,q)-Cluster Graphs ⋮ Alternative Parameterizations for Cluster Editing ⋮ Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correlation clustering
• Graph-modeled data clustering: Exact algorithms for clique generation
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• NP-hard problems in hierarchical-tree clustering
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
• The Cluster Editing Problem: Implementations and Experiments
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants
• A More Effective Linear Kernelization for Cluster Editing
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Fixed-Parameter Algorithms for Cluster Vertex Deletion
• Computing and Combinatorics

This page was built for publication: Fixed-parameter enumerability of cluster editing and related problems