CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

On the fixed-parameter enumerability of cluster editing

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
31st International Workshop on Graph-Theoretic Concepts in Computer Science WG 2005, Lecture Notes in Computer Science Vol. 3787 (2005), p. 283-294.
[Konferensbidrag, refereegranskat]

Cluster Editing is the problem of changing a graph G by at most k edge insertions or deletions into a disjoint union of cliques. The problem is motivated from computational biology and known to be fixed-parameter tractable (FPT). We study the enumeration of all solutions with a minimal set of edge changes. Enumerations can support efficient decisions between ambiguous solutions. We prove that all minimal solutions differ only on a so-called full kernel of at most k^2/4 vertices. This bound is tight. For ambiguous edges we get an optimal bound up to a constant factor. Finally we give an algorithm that outputs a compressed enumeration in O(2.4^k) time.

Nyckelord: clustering, parameterized complexity, enumeration

Denna post skapades 2006-08-25. Senast ändrad 2015-02-11.
CPL Pubid: 9637