nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

The State of the Art in Dynamic Graph Algorithms

verfasst von : Monika Henzinger

Erschienen in: SOFSEM 2018: Theory and Practice of Computer Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A dynamic graph algorithm is a data structure that supports operations on dynamically changing graphs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On Architecture Specification

Nächstes Kapitel Diversity in UML Modeling Explained: Observations, Classifications and Theorizations

There are still some openresearch question regarding the amortized versus the worst-case time per operation, but we will not discuss them here.

Note, however, that this does not exclude an algorithm that takes time \(O(m^{1/2})\) for both updates and queries.

Abboud, A., Dahlgaard, S.: Popular conjectures as a barrier for dynamic planar graph algorithms. In: FOCS (2016)

Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: FOCS (2014)

Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 782–793. Society for Industrial and Applied Mathematics (2010)

Agarwal, P.K., Eppstein, D., Guibas, L.J., Henzinger, M.R.: Parametric and kinetic minimum spanning trees. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 596–605. IEEE (1998)

Anand, A., Baswana, S., Gupta, M., Sen, S.: Maintaining approximate maximum weighted matching in fully dynamic graphs. In: D’Souza, D., Kavitha, T., Radhakrishnan, J. (eds.) FSTTCS. LIPIcs, vol. 18, pp. 257–266. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)

Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. J. Algorithms 31(1), 1–28 (1999)MathSciNetCrossRefMATH

Baswana, S., Gupta, M., Sen, S.: Fully dynamic maximal matching in \(\cal{O}(\log n)\) update time. In: FOCS (2011). http://dx.doi.org/10.1137/130914140

Bernstein, A., Karger, D.: A nearly optimal oracle for avoiding failed vertices and edges. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 101–110. ACM (2009)

Bernstein, A., Stein, C.: Fully dynamic matching in bipartite graphs. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 167–179. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47672-7_14 CrossRef

10.

Bernstein, A., Stein, C.: Faster fully dynamic matchings with small approximation ratios. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 692–711. Society for Industrial and Applied Mathematics (2016)

11.

Bhattacharya, S., Chakrabarty, D., Henzinger, M.: Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. In: Eisenbrand, F., Koenemann, J. (eds.) IPCO 2017. LNCS, vol. 10328, pp. 86–98. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59250-3_8 CrossRef

12.

Bhattacharya, S., Henzinger, M., Italiano, G.F.: Deterministic fully dynamic data structures for vertex cover and matching. In: SODA (2015)

13.

Bhattacharya, S., Henzinger, M., Nanongkai, D.: New deterministic approximation algorithms for fully dynamic matching. In: STOC 2016

14.

Bhattacharya, S., Henzinger, M., Nanongkai, D.: Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 470–489. SIAM (2017)

15.

Chan, T.M.: Dynamic subgraph connectivity with geometric applications. SIAM J. Comput. 36(3), 681–694 (2006)MathSciNetCrossRefMATH

16.

Chechik, S., Langberg, M., Peleg, D., Roditty, L.: F-sensitivity distance oracles and routing schemes. Algorithmica 63(4), 861–882 (2012)MathSciNetCrossRefMATH

17.

Dahlgaard, S.: On the hardness of partially dynamic graph problems and connections to diameter. In: ICALP, pp. 48:1–48:14 (2016)

18.

Duan, R., Pettie, S.: Connectivity oracles for failure prone graphs. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 465–474. ACM (2010)

19.

Eppstein, D., Galil, Z., Italiano, G.F., Spencer, T.H.: Separator based sparsification for dynamic planar graph algorithms. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pp. 208–217. ACM (1993)

20.

Frigioni, D., Italiano, G.F.: Dynamically switching vertices in planar graphs. Algorithmica 28(1), 76–103 (2000)MathSciNetCrossRefMATH

21.

Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Fully dynamic algorithms for maintaining shortest paths trees. J. Algorithms 34(2), 251–281 (2000)MathSciNetCrossRefMATH

22.

Gupta, M., Peng, R.: Fully dynamic \((1+\epsilon )\)-approximate matchings. In: FOCS (2013)

23.

Henzinger, M., Krinninger, S., Nanongkai, D.: Decremental single-source shortest paths on undirected graphs in near-linear total update time. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 146–155. IEEE (2014)

24.

Henzinger, M., Krinninger, S., Nanongkai, D., Saranurak, T.: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: STOC (2015)

25.

Henzinger, M., Lincoln, A., Neumann, S., Williams, V.V.: Conditional hardness for sensitivity problems. In: ITCS (2017)

26.

Henzinger, M., Neumann, S.: Incremental and fully dynamic subgraph connectivity for emergency planning. In: ESA (2016)

27.

Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM (JACM) 46(4), 502–516 (1999)MathSciNetCrossRefMATH

28.

Henzinger, M.R., Fredman, M.L.: Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22(3), 351–362 (1998)MathSciNetCrossRefMATH

29.

Holm, J., De Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM (JACM) 48(4), 723–760 (2001)MathSciNetCrossRefMATH

30.

Italiano, G.F., La Poutré, J.A., Rauch, M.H.: Fully dynamic planarity testing in planar embedded graphs. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol. 726, pp. 212–223. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57273-2_57

31.

Klein, P.N., Subramanian, S.: A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica 22(3), 235–249 (1998)MathSciNetCrossRefMATH

32.

Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3 sum conjecture. In: SODA, pp. 1272–1287 (2016)

33.

Larsen, K.G., Weinstein, O., Yu, H.: Crossing the logarithmic barrier for dynamic boolean data structure lower bounds. arXiv preprint arXiv:1703.03575 (2017)

34.

Neiman, O., Solomon, S.: Simple deterministic algorithms for fully dynamic maximal matching. In: STOC (2013)

35.

Patrascu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35(4), 932–963 (2006)MathSciNetCrossRefMATH

36.

Patrascu, M., Thorup, M.: Planning for fast connectivity updates. In: 48th Annual IEEE Symposium on Foundations of Computer Science, 2007, FOCS 2007, pp. 263–271. IEEE (2007)

37.

Peleg, D., Solomon, S.: Dynamic (1+\(\epsilon \))-approximate matchings: a density-sensitive approach. In: SODA (2016)

38.

Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: SODA (2007)

39.

Solomon, S.: Fully dynamic maximal matching in constant update time. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 325–334. IEEE (2016)

40.

Subramanian, S.: A fully dynamic data structure for reachability in planar digraphs. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol. 726, pp. 372–383. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57273-2_72

Titel: The State of the Art in Dynamic Graph Algorithms
verfasst von: Monika Henzinger
Verlag: Springer International Publishing
Buch: SOFSEM 2018: Theory and Practice of Computer Science
Print ISBN: 978-3-319-73116-2

Electronic ISBN: 978-3-319-73117-9

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-73117-9_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"