ON CONSTRUCTING MINIMUM SPANNING-TREES IN R-1(K)

Authors
BESPAMYATNIKH SN
Citation
Sn. Bespamyatnikh, ON CONSTRUCTING MINIMUM SPANNING-TREES IN R-1(K), Algorithmica, 18(4), 1997, pp. 524-529
Citations number
9
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
18
Issue
4
Year of publication
1997
Pages
524 - 529
Database
ISI
SICI code
0178-4617(1997)18:4<524:OCMSIR>2.0.ZU;2-K
Abstract
We give an algorithm to find a minimum spanning tree in the k-dimensio nal space under rectilinear metric. The running time is O((8(k)/root k )n(lg n)(k-2) Ig Ig n) for k greater than or equal to 3. This improves the previous bound by a factor root k lg(2) n/4(k).