Optimal parallel verification of minimum spanning trees in logarithmic time

被引：13

作者：

Dixon, B ^{[1
]}

Tarjan, RE ^{[1
]}

机构：

[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

来源：

ALGORITHMICA | 1997年 / 17卷 / 01期

关键词：

minimum spanning tree; network optimization; verification algorithms; sensitivity analysis;

D O I：

10.1007/BF02523235

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees. Our algorithms are deterministic and run in 0 (log n) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan.

引用

页码：11 / 18

页数：8

共 16 条

[1]

ALON N, UNPUB OPT PREPR ANSW

[2]

AWERBUCH B, 1987, IEEE T COMPUT, V36, P1258, DOI 10.1109/TC.1987.1676869

[3]

BOOTH H, 1990, TR768 YAL U DEP COMP

[4]

COLE R, 1994, P 6 ACM S PAR ALG AR