On constructing minimum spanning trees in R-1(k)

被引：1
|
作者：
Bespamyatnikh, SN
机构：
[1] Dept. of Mathematics and Mechanics, Ural State University, 51 Lenin St.
来源：
ALGORITHMICA | 1997年 / 18卷 / 04期
关键词：
minimum spanning tree; region approach; analysis of algorithm;
D O I：
10.1007/PL00009170
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We give an algorithm to find a minimum spanning tree in the k-dimensional 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).
引用
收藏
页码：524 / 529
页数：6
相关论文
共 50 条
12345