Faster Deterministic Fully-Dynamic Graph Connectivity

Abstract

Previous chapter Next chapter Full AccessProceedings Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Faster Deterministic Fully-Dynamic Graph ConnectivityChristian Wulff-NilsenChristian Wulff-Nilsenpp.1757 - 1769Chapter DOI:https://doi.org/10.1137/1.9781611973105.126PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We give new deterministic bounds for fully-dynamic graph connectivity. Our data structure supports updates (edge insertions/deletions) in O(log2 n/ 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. Previous chapter Next chapter RelatedDetails Published:2013ISBN:978-1-61197-251-1eISBN:978-1-61197-310-5 https://doi.org/10.1137/1.9781611973105Book Series Name:ProceedingsBook Code:PR143Book Pages:xix + 1915

Locations

• arXiv (Cornell University) - View - PDF