An improved algorithm for hierarchical clustering using strong components

Robert E. Tarjan

doi:10.1016/0020-0190(83)90088-1

An improved algorithm for hierarchical clustering using strong components

Robert E. Tarjan

Research output: Contribution to journal › Article › peer-review

23 Scopus citations

Abstract

In 1982 the author presented an O(m(log n)²) 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 language	English (US)
Pages (from-to)	37-41
Number of pages	5
Journal	Information Processing Letters
Volume	17
Issue number	1
DOIs	https://doi.org/10.1016/0020-0190(83)90088-1
State	Published - Jul 19 1983
Externally published	Yes

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

Access to Document

10.1016/0020-0190(83)90088-1

Cite this

@article{69725be531e4490193cdc115393dc249,

title = "An improved algorithm for hierarchical clustering using strong components",

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).",

keywords = "Cluster analysis, divide-and-conquer, graph algorithm, hierarchical decomposition, strong components",

author = "Tarjan, {Robert E.}",

year = "1983",

month = jul,

day = "19",

doi = "10.1016/0020-0190(83)90088-1",

language = "English (US)",

volume = "17",

pages = "37--41",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - An improved algorithm for hierarchical clustering using strong components

AU - Tarjan, Robert E.

PY - 1983/7/19

Y1 - 1983/7/19

N2 - 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).

AB - 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).

KW - Cluster analysis

KW - divide-and-conquer

KW - graph algorithm

KW - hierarchical decomposition

KW - strong components

UR - http://www.scopus.com/inward/record.url?scp=0020787001&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0020787001&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(83)90088-1

DO - 10.1016/0020-0190(83)90088-1

M3 - Article

AN - SCOPUS:0020787001

SN - 0020-0190

VL - 17

SP - 37

EP - 41

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

An improved algorithm for hierarchical clustering using strong components

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this