Login
- Document type:
- Technical Report
- Author(s):
- Klaus Holzapfel; Sven Kosub; Moritz G. Maaß; Hanjo Täubig
- Title:
- 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}). - Keywords:
- Density-based clustering; computational complexity; graph algorithms; fixed-parameter problems
- Year:
- 2002
- Year / month:
- 2002-12-01 00:00:00
- Pages:
- 16
BibTeX