Deterministic Incremental Triconnectivity in $O(\log^2 n)$ Worst-Case Time
Niels Inselmann Christiansen, Eva Rotenberg
原文摘要
We consider the problem of maintaining the triconnectivity in a graph $G$ in the incremental dynamic setting. We consider updates in the form of edge insertions and edge subdivisions, and triconnectivity queries, i.e. queries that take as input variables the vertices $a$ and $b$ and are of the form ''are there at least three vertex disjoint paths between $a$ and $b$?''. All algorithms presented in this paper are deterministic. When starting from a biconnected graph, all updates take worst-case $O(\log n)$ time, and all queries are answered in $O(\log n)$ time. By combining this result for biconnected graphs with a result of Holm and Rotenberg [SODA'20] we get a deterministic algorithm for general graphs with a worst-case update and query time of $O(\log^2 n)$. Both algorithms represent an improvement of the state-of-the-art by a factor of $O(\log n)$.
cs.DS