2005/06/29 by Jiri Sima, Jiřı́ Šı́ma, Sima, Jiri +2
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Graph Theory and Algorithms #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0506100
9 pages, no figures
arxiv created 2005/06/29 · openalex publication_date 2005/06/29 · arxiv updated 2009/12/01 · openalex created_date 2016/10/07 · openalex updated_date 2026/07/28
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.