VERIFICATION AND SENSITIVITY ANALYSIS OF MINIMUM SPANNING-TREES IN LINEAR TIME

被引：76

作者：

DIXON, B

RAUCH, M

TARJAN, RE

机构：

来源：

SIAM JOURNAL ON COMPUTING | 1992年 / 21卷 / 06期

关键词：

NETWORK OPTIMIZATION; MINIMUM SPANNING TREE; PROGRAM CHECKING; SENSITIVITY ANALYSIS; DIVIDE AND CONQUER;

D O I：

10.1137/0221070

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Komlos has devised a way to use a linear number of binary comparisons to test whether a given spanning tree of a graph with edge costs is a minimum spanning tree. The total computational work required by his method is much larger than linear, however. This paper describes a linear-time algorithm for verifying a minimum spanning tree. This algorithm combines the result of Komlos with a preprocessing and table look-up method for small subproblems and with a previously known almost-linear-time algorithm. Additionally, an optimal deterministic algorithm and a linear-time randomized algorithm for sensitivity analysis of minimum spanning trees are presented.

引用

页码：1184 / 1192

页数：9

共 21 条

[1]

[Anonymous], 1983, DATA STRUCTURES NETW, DOI DOI 10.1137/1.9781611970265

[2] THE COMPLEXITY OF ELEMENTARY ALGEBRA AND GEOMETRY [J].

BENOR, M ;

KOZEN, D ;

REIF, J .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1986, 32 (02) :251-264

[3]

BOOTH H, 1990, TR768 YAL U DEP COMP

[4]

BOOTH H, IN PRESS ALGORITHMIC

[5] TRIANGULATING A SIMPLE POLYGON IN LINEAR TIME [J].

CHAZELLE, B .

DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (05) :485-524

[6]

CHAZELLE B, 1990, CSTR24990 PRINC U

[7]

CHAZELLE B, 1990, 31ST P ANN IEEE S F, V1, P220

[8]

Fredman M. L., 1976, SIAM Journal on Computing, V5, P83, DOI 10.1137/0205006

[9]

FREDMAN ML, 1990, 31ST P ANN IEEE S F, V2, P719

[10] A LINEAR-TIME ALGORITHM FOR A SPECIAL CASE OF DISJOINT SET UNION [J].

GABOW, HN ;

TARJAN, RE .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 30 (02) :209-221

← 1 2 3 →