On the NP-Completeness of Some Graph Cluster Measures

Simple item page
dc.creatorSima, Jiri
dc.creatorSchaeffer, Satu Elisa
dc.date2005-06-29
dc.date.accessioned2026-07-07T03:23:11Z
dc.date.available2026-07-07T03:23:11Z
dc.descriptionGraph 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.
dc.description9 pages, no figures
dc.identifierhttps://arxiv.org/abs/cs/0506100
dc.identifierhttp://arxiv.org/abs/cs/0506100
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32844
dc.subjectComputational Complexity
dc.titleOn the NP-Completeness of Some Graph Cluster Measures
dc.typetext

Files

Collections

arXiv