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

Fixed-parameter tractable generalizations of cluster editing

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
6th International Conference on Algorithms and Complexity CIAC 2006, Lecture Notes in Computer Science Vol. 3998 (2006), p. 344-355.
[Konferensbidrag, refereegranskat]

In the Cluster Editing problem, a graph has to be changed to a disjoint union of cliques by at most k edge insertions or deletions. Several reasons suggest a generalized problem where the target graph can have some overlapping cliques. We show that the problem remains fixed-parameter tractable (FPT) in the combination of both parameters: k and a second parameter t describing somehow the complexity of overlap structure. For this result we need a structural property of twins in graphs enabling a certain elimination scheme that finally leads to a small enough subgraph we can branch on. We also give a nontrivial algorithm for the problem of minimizing the number of disjoint clusters, based on a concise enumeration of all solutions to the original Cluster Editing problem. This generic scheme may become interesting also for other multicriteria FPT problems.



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