- Title
- Graph-based data clustering with overlaps
- Creator
- Fellows, Michael R.; Guo, Jiong; Komusiewicz, Christian; Niedermeier, Rolf; Uhlmann, Joannes
- Relation
- 15th Annual International Conference, Computing and Combinatorics (COCOON 2009). Computing and Combinatorics 15th Annual International Conference, COCOON 2009 Proceedings (Niagara Falls, NY 13-15 July, 2009) p. 516-526
- Publisher Link
- http://dx.doi.org/10.1007/978-3-642-02882-3_51
- Publisher
- Springer Berlin
- Resource Type
- conference paper
- Date
- 2009
- Description
- We introduce overlap cluster graph modification problems where, other than in most previous work, 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 (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 complete complexity dichotomy (polynomial-time solvable vs NP-complete) 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 results (in case of constant s-values) and parameterized hardness (in case of unbounded s-values).
- Subject
- graphs; overlap cluster graph modification; edge modifications; parameterized complexity
- Identifier
- http://hdl.handle.net/1959.13/919432
- Identifier
- uon:8860
- Identifier
- ISBN:9783642028816
- Language
- eng
- Reviewed
- Hits: 2915
- Visitors: 2853
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|