Fast Parallel Recognition of Ultrametrics and Tree Metrics
Elias Dahlhaus · SIAM Journal on Discrete Mathematics · 1993
A fast parallel algorithm for the recognition of ultrametrics is presented. Its time-processor product is of the same order as the time bound of the known sequential algorithm of Culberson and Rudnicki [Inform. Process. Lett., 30 (1990), pp. 215–220] (compare also [SIAM J. Disc. Math., 3 (1990), pp. 1–6] and [Quart. Appl. Math., 26 (1968), pp. 607–609]. By the same way, tree metrics also can be recognized.