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

Even faster parameterized cluster deletion and cluster editing

Sebastian Böcker ; Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
Information Processing Letters (0020-0190). Vol. 111 (2011), 14, p. 717-721.
[Artikel, refereegranskad vetenskaplig]

Cluster Deletion and Cluster Editing ask to transform a graph by at most k edge deletions or edge edits, respectively, into a cluster graph, i.e., disjoint union of cliques. Equivalently, a cluster graph has no conflict triples, i.e., two incident edges without a transitive edge. We solve the two problems in time O(1.415^k) and O(1.76^k), respectively. These results round off our earlier work by considerably improved time bounds. For Cluster Deletion we use a technique that cuts away small connected components that do no longer contribute to the exponential part of the time complexity. As this idea is simple and versatile, it may lead to improvements for several other parameterized graph problems. The improvement for Cluster Editing is achieved by using the full power of an earlier structure theorem for graphs where no edge is in three conflict triples.

Nyckelord: graph algorithms, cluster editing, parameterized complexity



Denna post skapades 2011-06-07. Senast ändrad 2015-02-11.
CPL Pubid: 141374

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)