Abstract
| Original language | English |
|---|---|
| Pages (from-to) | 2-17 |
| Number of pages | 16 |
| Journal | Discrete Optimization |
| Volume | 8 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 2011 |
Fingerprint
Cite this
}
Graph-based data clustering with overlaps. / Fellows, Michael; Guo, Jiong; Komusiewicz, Christian; Niedermeier, Rolf; Uhlmann, Johannes.
In: Discrete Optimization, Vol. 8, No. 1, 2011, p. 2-17.Research output: Contribution to journal › Article › Research › peer-review
TY - JOUR
T1 - Graph-based data clustering with overlaps
AU - Fellows, Michael
AU - Guo, Jiong
AU - Komusiewicz, Christian
AU - Niedermeier, Rolf
AU - Uhlmann, Johannes
PY - 2011
Y1 - 2011
N2 - We introduce overlap cluster graph modification problems where, other than in most previous works, the clusters of the target graph may overlap. More precisely, the studied graph problems ask for a minimum number of edge modifications such that the resulting graph consists of clusters (that is, maximal cliques) that may overlap up to a certain amount specified by the overlap number s. In the case of s-vertex-overlap, each vertex may be part of at most s maximal cliques; s-edge-overlap is analogously defined in terms of edges. We provide a complexity dichotomy (polynomial-time solvable versus NP-hard) for the underlying edge modification problems, develop forbidden subgraph characterizations of "cluster graphs with overlaps", and study the parameterized complexity in terms of the number of allowed edge modifications, achieving fixed-parameter tractability (in case of constant s-values) and parameterized hardness (in case of unbounded s-values).
AB - We introduce overlap cluster graph modification problems where, other than in most previous works, the clusters of the target graph may overlap. More precisely, the studied graph problems ask for a minimum number of edge modifications such that the resulting graph consists of clusters (that is, maximal cliques) that may overlap up to a certain amount specified by the overlap number s. In the case of s-vertex-overlap, each vertex may be part of at most s maximal cliques; s-edge-overlap is analogously defined in terms of edges. We provide a complexity dichotomy (polynomial-time solvable versus NP-hard) for the underlying edge modification problems, develop forbidden subgraph characterizations of "cluster graphs with overlaps", and study the parameterized complexity in terms of the number of allowed edge modifications, achieving fixed-parameter tractability (in case of constant s-values) and parameterized hardness (in case of unbounded s-values).
KW - Fixed-parameter tractability
KW - Forbidden subgraph characterization
KW - Graph modifications
KW - Kernelization
KW - NP-hardness
KW - W [1]-hardness
KW - Characterization
KW - Hardness
KW - Parameter estimation
KW - Clustering algorithms
UR - http://www.scopus.com/inward/record.url?scp=79952186886&partnerID=8YFLogxK
U2 - 10.1016/j.disopt.2010.09.006
DO - 10.1016/j.disopt.2010.09.006
M3 - Article
VL - 8
SP - 2
EP - 17
JO - Discrete Optimization
JF - Discrete Optimization
SN - 1572-5286
IS - 1
ER -