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

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item