Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

被引：289

作者：

Holm, J ^{[1
]}

De Lichtenberg, K ^{[1
]}

Thorup, M ^{[1
]}

机构：

[1] AT&T Labs Res, Shannon Lab, Florham Pk, NJ 07932 USA

来源：

JOURNAL OF THE ACM | 2001年 / 48卷 / 04期

关键词：

algorithms; biconnectivity; connectivity; dynamic graph algorithms; minimum spanning tree; 2-edge connectivity;

D O I：

10.1145/502090.502095

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O (log(2) n) for connectivity, O (log(4) n) for minimum spanning forest, 2-edge connectivity, and O (log(5) n) biconnectivity.

引用

页码：723 / 760

页数：38

共 33 条

[1]

Alstrup S, 1997, LECT NOTES COMPUT SC, V1256, P270

[2] Efficient algorithms for Petersen's matching theorem [J].