Abstract
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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
| Editors | Sanjeev Khanna |
| Number of pages | 13 |
| Publisher | Association for Computing Machinery |
| Publication date | 2013 |
| Pages | 1757-1769 |
| ISBN (Print) | 978-1-61197-251-1 |
| ISBN (Electronic) | 978-1-61197-310-5 |
| DOIs | |
| Publication status | Published - 2013 |
| Event | Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Aster Crowne Plaza Hotel, New Orleans, United States Duration: 6 Jan 2013 → 8 Jan 2013 Conference number: 24 |
Conference
| Conference | Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| Number | 24 |
| Location | Aster Crowne Plaza Hotel |
| Country/Territory | United States |
| City | New Orleans |
| Period | 06/01/2013 → 08/01/2013 |