### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P. (2010) *Fixed-parameter enumerability of cluster editing and related problems*.

** BibTeX **

@article{

Damaschke2010,

author={Damaschke, Peter},

title={Fixed-parameter enumerability of cluster editing and related problems},

journal={Theory of Computing Systems},

issn={1432-4350},

volume={46},

issue={2},

pages={261-283},

abstract={Cluster Editing is transforming a graph by at most k edge insertions or deletions into a disjoint union of cliques. This problem is fixed-parameter tractable (FPT). Here we compute concise enumerations of all minimal solutions in
O(2.27^k+k^2n+m) time. Such enumerations support efficient inference procedures, but also the optimization of further objectives such as minimizing the number of clusters. In an extended problem version, target graphs may have a limited number of overlaps of cliques, measured by the number t of edges that remain when the twin vertices are merged. This problem is still in FPT, with respect to the combined parameter k and t. The result is based on a property of twin-free graphs. We also give FPT results for problem versions avoiding certain artificial clusterings. Furthermore, we prove that all solutions with minimal edit sequences differ on a so-called full kernel with at most k^2/4+O(k) vertices, that can be found in polynomial time. The size bound is tight. We also get a bound for the number of edges in the full kernel, which is optimal up to a (large) constant factor. Numerous open problems are mentioned.},

year={2010},

keywords={cluster graphs, soft clustering, fixed-parameter tractability, enumeration problems, true twins},

}

** RefWorks **

RT Journal Article

SR Print

ID 111001

A1 Damaschke, Peter

T1 Fixed-parameter enumerability of cluster editing and related problems

YR 2010

JF Theory of Computing Systems

SN 1432-4350

VO 46

IS 2

SP 261

OP 283

AB Cluster Editing is transforming a graph by at most k edge insertions or deletions into a disjoint union of cliques. This problem is fixed-parameter tractable (FPT). Here we compute concise enumerations of all minimal solutions in
O(2.27^k+k^2n+m) time. Such enumerations support efficient inference procedures, but also the optimization of further objectives such as minimizing the number of clusters. In an extended problem version, target graphs may have a limited number of overlaps of cliques, measured by the number t of edges that remain when the twin vertices are merged. This problem is still in FPT, with respect to the combined parameter k and t. The result is based on a property of twin-free graphs. We also give FPT results for problem versions avoiding certain artificial clusterings. Furthermore, we prove that all solutions with minimal edit sequences differ on a so-called full kernel with at most k^2/4+O(k) vertices, that can be found in polynomial time. The size bound is tight. We also get a bound for the number of edges in the full kernel, which is optimal up to a (large) constant factor. Numerous open problems are mentioned.

LA eng

DO 10.1007/s00224-008-9130-1

OL 30