Benutzer: Gast  Login
Dokumenttyp:
Technical Report 
Autor(en):
Klaus Holzapfel; Sven Kosub; Moritz G. Maaß; Hanjo Täubig 
Titel:
The complexity of detecting fixed-density clusters 
Abstract:
We study the complexity of finding a subgraph of a certain size and a certain density, where density is measured by the average degree. Let g be any density function, i.e., g is computable in polynomial time and satisfies g(k)0 and has a polynomial-time algorithm for g=2+ O(k^{-1}). 
Stichworte:
Density-based clustering; computational complexity; graph algorithms; fixed-parameter problems 
Jahr:
2002 
Jahr / Monat:
2002-12-01 00:00:00 
Seiten/Umfang:
16