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

Křivánek, Mirko

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.

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

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