On the NP-Completeness of Some Graph Cluster Measures

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F06%3A00339971" target="_blank" >RIV/67985807:_____/06:00339971 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
On the NP-Completeness of Some Graph Cluster Measures
Popis výsledku v původním jazyce
Graph clustering is the problem of identifying sparsely connected dense subgraphs (clusters) in a given graph. Identifying clusters can be achieved by optimizing a fitness function that measures the quality of a cluster within the graph. Examples of suchcluster 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 clusters that are optimal with respect to these fitness measures are NP-complete.
Název v anglickém jazyce
On the NP-Completeness of Some Graph Cluster Measures
Popis výsledku anglicky
Graph clustering is the problem of identifying sparsely connected dense subgraphs (clusters) in a given graph. Identifying clusters can be achieved by optimizing a fitness function that measures the quality of a cluster within the graph. Examples of suchcluster 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 clusters that are optimal with respect to these fitness measures are NP-complete.

Projekt
<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2006
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)