FAST PARALLEL RECOGNITION OF ULTRAMETRICS AND TREE METRICS

Authors
DAHLHAUS E
Citation
E. Dahlhaus, FAST PARALLEL RECOGNITION OF ULTRAMETRICS AND TREE METRICS, SIAM journal on discrete mathematics, 6(4), 1993, pp. 523-532
Citations number
20
Categorie Soggetti
Mathematics,Mathematics
Journal title
SIAM journal on discrete mathematics → ACNP
ISSN journal
08954801
Volume
6
Issue
4
Year of publication
1993
Pages
523 - 532
Database
ISI
SICI code
0895-4801(1993)6:4<523:FPROUA>2.0.ZU;2-E
Abstract
A fast parallel algorithm for the recognition of ultrametrics is prese nted. Its time-processor product is of the same order as the time boun d 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-60 9]. By the same way, tree metrics also can be recognized.