TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 01.11.2018


Page Content

to Navigation

Parameterized Dynamic Cluster Editing

Junjie Luo (TU Berlin, University of Chinese Academy of Sciences)

We introduce a dynamic version of the NP-hard Cluster Editing problem. The essential point here is to take into account dynamically evolving input graphs: Having a cluster graph (that is, a disjoint union of cliques) that represents a solution for a first input graph, can we cost-efficiently transform it into a "similar" cluster graph that is a solution for a second ("subsequent") input graph? This model is motivated by several application scenarios, including incremental clustering, the search for compromise clusterings, or also local search in graph-based data clustering. We thoroughly study six problem variants (edge editing, edge deletion, edge insertion; each combined with two distance measures between cluster graphs). We obtain both fixed-parameter tractability as well as parameterized hardness results, thus (except for two open questions) providing a fairly complete picture of the parameterized computational complexity landscape under the perhaps two most natural parameterizations: the distance of the new "similar" cluster graph to (i) the second input graph and to (ii) the input cluster graph.



Junjie Luo
TEL 512

Back to the research colloquium site.

To top


Quick Access

Schnellnavigation zur Seite über Nummerneingabe