An improved algorithm for hierarchical clustering using strong components

Research output: Contribution to journalArticle

21 Scopus citations

Abstract

In 1982 the author presented an O(m(log n)2) time algorithm for hierarchically decomposing a directed n-vertex, m-edge graph with weighted edges into strong components. Such an algorithm is useful in cluster analysis of data with an asymmetric similarity measure. The present paper gives a simpler algorithm with the faster running time of O(m log n).

Original languageEnglish (US)
Pages (from-to)37-41
Number of pages5
JournalInformation Processing Letters
Volume17
Issue number1
DOIs
StatePublished - Jul 19 1983
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Cluster analysis
  • divide-and-conquer
  • graph algorithm
  • hierarchical decomposition
  • strong components

Fingerprint Dive into the research topics of 'An improved algorithm for hierarchical clustering using strong components'. Together they form a unique fingerprint.

  • Cite this