返回Google圖書搜尋

Poly-logarithmic Deterministic Fully Dynamic Graph Algorithms II

其他書名	2-edge and Bioconnectivity
出版	Datalogisk Institut, Københavns Universitet, 1997
URL	http://books.google.com.hk/books?id=Ws36tgEACAAJ&hl=&source=gbs_api

註釋Abstract: "Deterministic fully dynamic algorithms are presented for 2-edge connectivity and biconnectivity. For 2-edge connectivity the amortized cost per operation is O(log4 n) improving over the previous best deterministic bound of O([square root n]) and the previous best randomized bound of O(log5 n). For biconnectivity the amortized cost per operation is also O(log4 n) improving over the previous best deterministic bound of O([square root n log n] log [m/n]) and the alternative randomized bound of O([delta] log4 n) where [delta] is the maximal degree. Thus our O(log4 n) bound is the first polylogarithmic bound for biconnectivity."