Faster deterministic fully-dynamic graph connectivity

TY - GEN

T1 - Faster deterministic fully-dynamic graph connectivity

AU - Wulff-Nilsen, Christian

N1 - Conference code: 24

PY - 2013

Y1 - 2013

N2 - We give new deterministic bounds for fully-dynamic graph connectivity. Our data structure supports updates (edge insertions/deletions) in O(log 2n/ log log n) amortized time and connectivity queries in O(log n/ log log n) worst-case time, where n is the number of vertices of the graph. This improves the deterministic data structures of Holm, de Lichtenberg, and Thorup (STOC 1998, J.ACM 2001) and Thorup (STOC 2000) which both have O(log2 n) amortized update time and O(log n/ log log n) worst-case query time. Our model of computation is the same as that of Thorup, i.e., a pointer machine with standard AC0 instructions.

AB - We give new deterministic bounds for fully-dynamic graph connectivity. Our data structure supports updates (edge insertions/deletions) in O(log 2n/ log log n) amortized time and connectivity queries in O(log n/ log log n) worst-case time, where n is the number of vertices of the graph. This improves the deterministic data structures of Holm, de Lichtenberg, and Thorup (STOC 1998, J.ACM 2001) and Thorup (STOC 2000) which both have O(log2 n) amortized update time and O(log n/ log log n) worst-case query time. Our model of computation is the same as that of Thorup, i.e., a pointer machine with standard AC0 instructions.

U2 - 10.1137/1.9781611973105.126

DO - 10.1137/1.9781611973105.126

M3 - Article in proceedings

SN - 978-1-61197-251-1

SP - 1757

EP - 1769

BT - Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Khanna, Sanjeev

PB - Association for Computing Machinery

T2 - Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 6 January 2013 through 8 January 2013

ER -