On the NP-Completeness of Some Graph Cluster Measures

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Graph clustering is the problem of identifying sparsely connected dense subgraphs (clusters) in a given graph. Proposed clustering algorithms usually optimize various fitness functions that measure the quality of a cluster within the graph. Examples of such cluster measures include the conductance, the local and relative densities, and single cluster editing. We prove that the decision problems associated with the optimization tasks of finding the clusters that are optimal with respect to these fitness measures are NP-complete.
9 pages, no figures

Keywords

Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/32844

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0506100
 http://arxiv.org/abs/cs/0506100

Collections

arXiv