Parameterized Dynamic Cluster Editing
Luo, Junjie1,2; Molter, Hendrik3; Nichterlein, Andre3; Niedermeier, Rolf3
Source PublicationALGORITHMICA
AbstractWe introduce a dynamic version of the NP-hard graph modification problemCluster Editing. The essential point here is to take into account dynamically evolving input graphs: having a cluster graph (that is, a disjoint union of cliques) constituting 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 (three modification scenarios 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 three open questions) providing a fairly complete picture of the parameterized computational complexity landscape under the two perhaps most natural parameterizations: the distances of the new "similar" cluster graph to (1) the second input graph and to (2) the input cluster graph.
KeywordGraph-based data clustering Incremental clustering Compromise clustering Correlation clustering Local search Goal-oriented clustering NP-hard problems Fixed-parameter tractability Parameterized complexity Kernelization Multi-choice knapsack
Indexed BySCI
Funding ProjectProjekt DEAL ; CAS-DAAD Joint Fellowship Program of UCAS ; DFG, Project AFFA[BR 5207/1] ; DFG, Project MATE[NI 369/17]
WOS Research AreaComputer Science ; Mathematics
WOS SubjectComputer Science, Software Engineering ; Mathematics, Applied
WOS IDWOS:000552516200002
Citation statistics
Document Type期刊论文
Corresponding AuthorMolter, Hendrik
Affiliation1.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China
2.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China
3.TU Berlin, Fac 4, Algorithm & Computat Complex, Berlin, Germany
Recommended Citation
GB/T 7714
Luo, Junjie,Molter, Hendrik,Nichterlein, Andre,et al. Parameterized Dynamic Cluster Editing[J]. ALGORITHMICA,2020:44.
APA Luo, Junjie,Molter, Hendrik,Nichterlein, Andre,&Niedermeier, Rolf.(2020).Parameterized Dynamic Cluster Editing.ALGORITHMICA,44.
MLA Luo, Junjie,et al."Parameterized Dynamic Cluster Editing".ALGORITHMICA (2020):44.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Luo, Junjie]'s Articles
[Molter, Hendrik]'s Articles
[Nichterlein, Andre]'s Articles
Baidu academic
Similar articles in Baidu academic
[Luo, Junjie]'s Articles
[Molter, Hendrik]'s Articles
[Nichterlein, Andre]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Luo, Junjie]'s Articles
[Molter, Hendrik]'s Articles
[Nichterlein, Andre]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.