Křivánek, Mirko The complexity of ultrametric partitions on graphs. (English) Zbl 0637.68047 Inf. Process. Lett. 27, No. 5, 265-270 (1988). 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. Cited in 10 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science Keywords:cluster analysis; automated design; VLSI circuits; ultrametric partitions; weighted complete graph; computational complexity; polynomial algorithm PDF BibTeX XML Cite \textit{M. Křivánek}, Inf. Process. Lett. 27, No. 5, 265--270 (1988; Zbl 0637.68047) Full Text: DOI OpenURL References: [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.