An approximation algorithm for clustering graphs with dominating diametral path

Jitender S. Deogun, Dieter Kratsch, George Steiner

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

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 languageEnglish (US)
Pages (from-to)121-127
Number of pages7
JournalInformation Processing Letters
Volume61
Issue number3
DOIs
StatePublished - Feb 14 1997
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'An approximation algorithm for clustering graphs with dominating diametral path'. Together they form a unique fingerprint.

Cite this