KMS Of Academy of mathematics and systems sciences, CAS
| Parameterized Dynamic Cluster Editing | |
| Luo, Junjie1,2; Molter, Hendrik3; Nichterlein, Andre3; Niedermeier, Rolf3 | |
| 2020-07-25 | |
| Source Publication | ALGORITHMICA
 |
| ISSN | 0178-4617 |
| Pages | 44 |
| Abstract | We 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. |
| Keyword | Graph-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 |
| DOI | 10.1007/s00453-020-00746-y |
| Indexed By | SCI |
| Language | 英语 |
| Funding Project | Projekt DEAL ; CAS-DAAD Joint Fellowship Program of UCAS ; DFG, Project AFFA[BR 5207/1] ; DFG, Project MATE[NI 369/17] |
| WOS Research Area | Computer Science ; Mathematics |
| WOS Subject | Computer Science, Software Engineering ; Mathematics, Applied |
| WOS ID | WOS:000552516200002 |
| Publisher | SPRINGER |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/51889 |
| Collection | 中国科学院数学与系统科学研究院 |
| Corresponding Author | Molter, Hendrik |
| Affiliation | 1.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. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment