LIPIcs.ISAAC.2017.59.pdf
- Filesize: 0.49 MB
- 12 pages
Document
Fully Dynamic Connectivity Oracles under General Vertex Updates
Author
-
Part of:
Volume:
28th International Symposium on Algorithms and Computation (ISAAC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-12-07
Cite As Get BibTex
Kengo Nakamura. Fully Dynamic Connectivity Oracles under General Vertex Updates. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ISAAC.2017.59
Abstract
We study the following dynamic graph problem: given an undirected graph G, we maintain a connectivity oracle between any two vertices in G under any on-line sequence of vertex deletions and insertions with incident edges. We propose two algorithms for this problem: an amortized update time deterministic one and a worst case update time Monte Carlo one. Both of them allow an arbitrary number of new vertices to insert. The update time complexity of the former algorithm is no worse than the existing algorithms, which allow only limited number of vertices to insert. Moreover, for relatively dense graphs, we can expect that the update time bound of the former algorithm meets a lower bound, and that of the latter algorithm can be seen as a substantial improvement of the existing result by introducing randomization.
Subject Classification
Keywords
- Dynamic Graph
- Connectivity
- Depth-First Search
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- I. Abraham, S. Chechik, and S. Krinninger. Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Proc. SODA, pages 440-452, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.28.
- S. Baswana, S. R. Chaudhury, K. Choudhary, and S. Khan. Dynamic DFS in undirected graphs: breaking the O(m) barrier. In Proc. SODA, pages 730-739, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch52.
- S. Baswana, A. Goel, and S. Khan. Incremental DFS algorithms: a theoretical and experimental study. arXiv:1705.02613, 2017. URL: http://arxiv.org/abs/1705.02613.
- D. Belazzougui and S. J. Puglisi. Range predecessor and Lempel-Ziv parsing. In Proc. SODA, pages 2053-2071, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch143.
- M. A. Bender and M. Farach-Colton. The LCA problem revisited. In Proc. LATIN, pages 88-94, 2000. URL: http://dx.doi.org/10.1007/10719839_9.
- T. M. Chan, M. Pǎtraşcu, and L. Roditty. Dynamic connectivity: connecting to networks and geometry. SIAM J. Comput., 40:333-349, 2011. URL: http://dx.doi.org/10.1137/090751670.
- R. Duan. New data structures for subgraph connectivity. In Proc. ICALP, Part I, pages 201-212, 2010. URL: http://dx.doi.org/10.1007/978-3-642-14165-2_18.
- R. Duan and L. Zhang. Faster randomized worst-case update time for dynamic subgraph connectivity. In Proc. WADS, pages 337-348, 2017. URL: http://dx.doi.org/10.1007/978-3-319-62127-2_29.
-
P. Erdős and A. Rényi. On random graphs I. Publ. Math., 6:290-297, 1959.
- B. M. Kapron, V. King, and B. Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proc. SODA, pages 1131-1142, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.81.
- C. Kejlberg-Rasmussen, T. Kopelowitz, S. Pettie, and M. Thorup. Faster worst case deterministic dynamic connectivity. In Proc. ESA, pages 53:1-53:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.53.
- K. Nakamura and K. Sadakane. A space-efficient algorithm for the dynamic DFS problem in undirected graphs. In Proc. WALCOM, pages 295-307, 2017. URL: http://dx.doi.org/10.1007/978-3-319-53925-6_23.
- D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26:362-391, 1983. URL: http://dx.doi.org/10.1016/0022-0000(83)90006-5.
- C. Wulff-Nilsen. Faster deterministic fully-dynamic graph connectivity. In Proc. SODA, pages 1757-1769, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.126.