Computer Science – Computational Complexity
Scientific paper
2005-06-29
Computer Science
Computational Complexity
9 pages, no figures
Scientific paper
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.
Schaeffer Satu Elisa
Sima Jiri
No associations
LandOfFree
On the NP-Completeness of Some Graph Cluster Measures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the NP-Completeness of Some Graph Cluster Measures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the NP-Completeness of Some Graph Cluster Measures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-84581