Abstract
The algorithmic complexity of the graph clustering problem when restricted to special classes of graphs is investigated. We develop results showing the intractability of graph clustering and the hardness of approximating minimum graph clusterings. Our main result is a polynomial time approximation algorithm of constant worst case ratio (at most 3) which computes a k-clustering for graphs having a dominating diametral path.
Original language | English (US) |
---|---|
Pages (from-to) | 121-127 |
Number of pages | 7 |
Journal | Information Processing Letters |
Volume | 61 |
Issue number | 3 |
DOIs | |
State | Published - Feb 14 1997 |
Keywords
- Approximation algorithms
- Design of algorithms
- Graph clustering
- Special graph classes
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications