Document Open Access Logo

Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning

Authors Monika Henzinger, Stefan Neumann

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.48.pdf
  • Filesize: 423 kB
  • 11 pages

Document Identifiers

Author Details

Monika Henzinger
Stefan Neumann

Cite As Get BibTex

Monika Henzinger and Stefan Neumann. Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 48:1-48:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.48

Abstract

During the last 10 years it has become popular to study dynamic graph problems in a emergency planning or sensitivity setting: Instead of considering the general fully dynamic problem, we only have to process a single batch update of size d; after the update we have to answer queries.

In this paper, we consider the dynamic subgraph connectivity problem with sensitivity d: We are given a graph of which some vertices are activated and some are deactivated. After that we get a single update in which the states of up to $d$ vertices are changed. Then we get a sequence of connectivity queries in the subgraph of activated vertices.

We present the first fully dynamic algorithm for this problem which has an update and query time only slightly worse than the best decremental algorithm. In addition, we present the first incremental algorithm which is tight with respect to the best known conditional lower bound; moreover, the algorithm is simple and we believe it is implementable and efficient in practice.

Subject Classification

Keywords
  • connectivity
  • emergency planning
  • sensitivity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 434-443, Philadelphia, PA, USA, 2014. Google Scholar
  2. Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan. Dynamic DFS tree in undirected graphs: breaking the O(m) barrier. CoRR, abs/1502.02481, 2015. Google Scholar
  3. Aaron Bernstein and David Karger. Improved distance sensitivity oracles via random sampling. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 34-43, Philadelphia, PA, USA, 2008. Google Scholar
  4. Aaron Bernstein and David Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing (STOC), pages 101-110, New York, NY, USA, 2009. Google Scholar
  5. Timothy M. Chan. Dynamic subgraph connectivity with geometric applications. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing (STOC), pages 7-13, New York, NY, USA, 2002. Google Scholar
  6. Timothy M Chan, Mihai Patrascu, and Liam Roditty. Dynamic connectivity: Connecting to networks and geometry. SIAM Journal on Computing, 40(2):333-349, 2011. Google Scholar
  7. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-sensitivity distance oracles and routing schemes. Algorithmica, 63(4):861-882, 2011. Google Scholar
  8. Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran. Oracles for distances avoiding a failed node or link. SIAM Journal on Computing, 37(5):1299-1318, 2008. Google Scholar
  9. Ran Duan. New data structures for subgraph connectivity. In 37th International Colloquium on Automata, Languages and Programming (ICALP), pages 201-212, Bordeaux, France, 2010. Google Scholar
  10. Ran Duan and Seth Pettie. Dual-failure distance and connectivity oracles. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 506-515, Philadelphia, PA, USA, 2009. Google Scholar
  11. Ran Duan and Seth Pettie. Connectivity oracles for failure prone graphs. In Proceedings of the Forty-second ACM Symposium on Theory of Computing (STOC), pages 465-474, New York, NY, USA, 2010. Google Scholar
  12. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. Journal of the ACM, 44(5):669-696, 1997. Google Scholar
  13. Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC), pages 252-257, New York, NY, USA, 1983. Google Scholar
  14. D. Frigioni and F. G. Italiano. Dynamically switching vertices in planar graphs. Algorithmica, 28(1):76-103, 2000. Google Scholar
  15. David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn. Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR, abs/1509.06464, 2015. Google Scholar
  16. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), pages 21-30, New York, NY, USA, 2015. Google Scholar
  17. Monika R. Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM, 46(4):502-516, 1999. Google Scholar
  18. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM, 48(4):723-760, 2001. Google Scholar
  19. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1131-1142, 2013. Google Scholar
  20. Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. Faster worst case deterministic dynamic connectivity. CoRR, abs/1507.05944, 2015. Google Scholar
  21. Neelesh Khanna and Surender Baswana. Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science (STACS), Leibniz International Proceedings in Informatics (LIPIcs), pages 513-524, 2010. Google Scholar
  22. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1272-1287, 2016. Google Scholar
  23. Mihai Patrascu and Mikkel Thorup. Planning for fast connectivity updates. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 263-271, 2007. Google Scholar
  24. Mikkel Thorup. Near-optimal fully-dynamic graph connectivity. In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing (STOC), pages 343-350, 2000. Google Scholar
  25. Christian Wulff-Nilsen. Faster deterministic fully-dynamic graph connectivity. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1757-1769, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact