Parameterized Dynamic Cluster Editing
文献类型：期刊论文
| 作者 | Luo, Junjie2,3; Molter, Hendrik1; Nichterlein, Andre1; Niedermeier, Rolf1 |
| 刊名 | ALGORITHMICA
 |
| 出版日期 | 2020-07-25 |
| 页码 | 44 |
| ISSN号 | 0178-4617 |
| 关键词 | 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 |
| 英文摘要 | 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. |
| 资助项目 | Projekt DEAL ; CAS-DAAD Joint Fellowship Program of UCAS ; DFG, Project AFFA[BR 5207/1] ; DFG, Project MATE[NI 369/17] |
| WOS研究方向 | Computer Science ; Mathematics |
| 语种 | 英语 |
| 出版者 | SPRINGER |
| WOS记录号 | WOS:000552516200002 |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/51888]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Molter, Hendrik |
| 作者单位 | 1.TU Berlin, Fac 4, Algorithm & Computat Complex, Berlin, Germany 2.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。