The complexity of ultrametric partitions on graphs. (English) Zbl 0637.68047

Summary: Partitioning of graphs has many practical applications namely in cluster analysis and in automated design of VLSI circuits. Using 1-1 correspondence between ultrametric partitions of a weighted complete graph K(w) on a finite set X and ultrametrics on X, the computational complexity of the appoximation of w by means of an ultrametric u is investigated and systematized. As a main result, a polynomial algorithm that solves the problem under some ‘min-max’ criterion is developed.


68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Diday, E.; Lemaire, J.; Pouget, J.; Testu, F., Elements d’analyse des donneés, (1982), Dunod Paris
[2] Edmonds, J.; Fulkerson, D.R., Bottleneck extrema, J. combin. theory, 8, 299-306, (1970) · Zbl 0218.05006
[3] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[4] Jardine, N.; Sibson, R., Mathematical taxonomy, (1979), Wiley London · Zbl 0322.62065
[5] Křivánek, M.; Morávek, J., NP-hard problems in hierarchical-tree clustering, Acta informatica, 23, 311-323, (1986) · Zbl 0644.68055
[6] Mehlhorn, K., Data structures and algorithms, Vol. 2, (1984), Springer Berlin
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.