Deterministic incremental triconnectivity updates in logarithmic time
Deterministic Incremental Triconnectivity in $O(\log^2 n)$ Worst-Case Time
Data Structures and Algorithms
Summary
This paper deals with how to efficiently keep track of strong connections in a network as it grows. The authors focus on triconnectivity, meaning there are at least three separate ways to get from one point to another. They present algorithms that can update and answer queries about these connections quickly and predictably every time the network changes. Their method improves the speed of previous solutions, making it faster to maintain such connectivity information in dynamic networks.
What this means in practice
- •For network infrastructure engineers: Maintain real-time robust connection checks in growing network topologies using faster incremental algorithms.
- •For database system developers: Implement efficient dynamic graph connectivity features that speed up query responses on evolving data relationships.
Authors
Niels Inselmann Christiansen, Eva Rotenberg
Abstract
We consider the problem of maintaining the triconnectivity in some biconnected 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 of the form "are there at least three vertex disjoint paths between a and b?". All algorithms presented in this paper are deterministic. All queries and updates are answered in worst-case $O(\log n)$ time. By combining this result for biconnected graphs with a result of Holm and Rotenberg [SODA'20] we get an algorithm for general graphs with a worst-case running time of $O(\log^2 n)$ per operation. These algorithms represent an improvement of the state-of-the-art by a factor of $O(\log n)$.