期刊
SIAM JOURNAL ON DISCRETE MATHEMATICS
卷 24, 期 4, 页码 1662-1683出版社
SIAM PUBLICATIONS
DOI: 10.1137/090767285
关键词
NP-hard problems; exact algorithms; fixed-parameter tractability; data reduction; graph modification; k-plex; dense subgraphs; forbidden subgraph characterization
资金
- Excellence Cluster on Multimodal Computing and Interaction (MMCI)
- Carl-Zeiss-Stiftung
- DFG [NI 369/7]
We introduce the s-Plex Cluster Editing problem as a generalization of the well-studied Cluster Editing problem; both are NP-hard and both are motivated by graph-based data clustering. Instead of transforming a given graph by a minimum number of edge modifications into a disjoint union of cliques (this is Cluster Editing), the task in the case of s-Plex Cluster Editing is to transform a graph into a cluster graph consisting of a disjoint union of so-called s-plexes. Herein, an s-plex is a vertex set S inducing a subgraph in which every vertex has degree at least vertical bar S vertical bar - s. Cliques are 1-plexes. The advantage of s-plexes for s >= 2 is that they allow us to model a more relaxed cluster notion (s-plexes instead of cliques), better reflecting inaccuracies of the input data. We develop a provably effective preprocessing based on data reduction (yielding a so-called problem kernel), a forbidden subgraph characterization of s-plex cluster graphs, and a depth-bounded search tree which is used to find optimal edge modification sets. Altogether, this yields efficient algorithms in case of moderate numbers of edge modifications; this is often a reasonable assumption under a maximum parsimony model for data clustering.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据