Parameterized Dynamic Cluster Editing

doi:10.1007/s00453-020-00746-y

CSpace

	Parameterized Dynamic Cluster Editing
	Luo, Junjie 1,2; Molter, Hendrik 3; Nichterlein, Andre 3; Niedermeier, Rolf 3
	2020-07-25
发表期刊	ALGORITHMICA
ISSN	0178-4617
页码	44
摘要	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.
关键词	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
收录类别	SCI
语种	英语
资助项目	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
WOS类目	Computer Science, Software Engineering ; Mathematics, Applied
WOS记录号	WOS:000552516200002
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/51889
专题	中国科学院数学与系统科学研究院
通讯作者	Molter, Hendrik
作者单位	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
推荐引用方式 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.