期刊
JOURNAL OF THE ACM
卷 48, 期 4, 页码 723-760出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/502090.502095
关键词
algorithms; biconnectivity; connectivity; dynamic graph algorithms; minimum spanning tree; 2-edge connectivity
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据