Document Open Access Logo

Recent Advances in Fully Dynamic Graph Algorithms (Invited Talk)

Authors Kathrin Hanauer , Monika Henzinger , Christian Schulz

PDF
Thumbnail PDF

File

LIPIcs.SAND.2022.1.pdf
  • Filesize: 1.09 MB
  • 47 pages

Document Identifiers

Author Details

Kathrin Hanauer
  • Faculty of Computer Science, Universität Wien, Austria
Monika Henzinger
  • Faculty of Computer Science, Universität Wien, Austria
Christian Schulz
  • Faculty of Mathematics and Computer Science, Universität Heidelberg, Germany

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564, "The Design of Modern Fully Dynamic Data Structures (MoDynStruct)"), as well as from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Moreover, we have been partially supported by DFG grant SCHU 2567/1-2.

Cite As Get BibTex

Kathrin Hanauer, Monika Henzinger, and Christian Schulz. Recent Advances in Fully Dynamic Graph Algorithms (Invited Talk). In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 1:1-1:47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SAND.2022.1

Abstract

In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms.

Subject Classification

ACM Subject Classification
  • General and reference → Surveys and overviews
  • Networks → Network dynamics
  • Mathematics of computing → Graph algorithms
Keywords
  • fully dynamic graph algorithms
  • survey

Metrics

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

References

  1. Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha. Dynamic set cover: improved algorithms and lower bounds. In Moses Charikar and Edith Cohen, editors, Proc. of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 114-125. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316376.
  2. Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 477-486. IEEE, 2016. Google Scholar
  3. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 434-443. IEEE, 2014. URL: https://doi.org/10.1109/FOCS.2014.53.
  4. Ittai Abraham, Shiri Chechik, and Sebastian Krinninger. Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 440-452. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.28.
  5. Ittai Abraham, Shiri Chechik, and Kunal Talwar. Fully dynamic all-pairs shortest paths: Breaking the o(n) barrier. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, volume 28 of LIPIcs, pages 1-16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.1.
  6. Umut A. Acar, Daniel Anderson, Guy E. Blelloch, and Laxman Dhulipala. Parallel batch-dynamic graph connectivity. In Christian Scheideler and Petra Berenbrink, editors, The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019, pages 381-392. ACM, 2019. URL: https://doi.org/10.1145/3323165.3323196.
  7. Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. Parallel batch-dynamic trees via change propagation. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 2:1-2:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.2.
  8. Nesreen K. Ahmed, Nick G. Duffield, Theodore L. Willke, and Ryan A. Rossi. On sampling from massive graph streams. Proc. VLDB Endow., 10(11):1430-1441, 2017. URL: https://doi.org/10.14778/3137628.3137651.
  9. Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling. In Chin-Wan Chung, Andrei Z. Broder, Kyuseok Shim, and Torsten Suel, editors, 23rd International World Wide Web Conference, WWW '14, Seoul, Republic of Korea, April 7-11, 2014, pages 237-248. ACM, 2014. URL: https://doi.org/10.1145/2566486.2568007.
  10. David Alberts, Giuseppe Cattaneo, and Giuseppe F. Italiano. An empirical study of dynamic graph algorithms. ACM J. Exp. Algorithmics, 2:5, 1997. URL: https://doi.org/10.1145/264216.264223.
  11. David Alberts, Giuseppe Cattaneo, Giuseppe F Italiano, Umberto Nanni, and Christos Zaroliagis. A software library of dynamic graph algorithms. In Proc. Workshop on Algorithms and Experiments, pages 129-136. Citeseer, 1998. Google Scholar
  12. Bowen Alpern, Roger Hoover, Barry K. Rosen, Peter F. Sweeney, and F. Kenneth Zadeck. Incremental evaluation of computational circuits. In David S. Johnson, editor, Proc. of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1990, San Francisco, California, USA, pages 32-42. SIAM, 1990. URL: http://dl.acm.org/citation.cfm?id=320176.320180.
  13. Hamidreza Alvari, Alireza Hajibagheri, and Gita Reese Sukthankar. Community detection in dynamic social networks: A game-theoretic approach. In Xindong Wu, Martin Ester, and Guandong Xu, editors, 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014, Beijing, China, August 17-20, 2014, pages 101-107. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/ASONAM.2014.6921567.
  14. Abhash Anand, Surender Baswana, Manoj Gupta, and Sandeep Sen. Maintaining approximate maximum weighted matching in fully dynamic graphs. In Deepak D'Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, volume 18 of LIPIcs, pages 257-266. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2012.257.
  15. Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams, and Nicole Wein. Algorithms and hardness for diameter in dynamic graphs. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 13:1-13:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.13.
  16. Eugenio Angriman, Henning Meyerhenke, Christian Schulz, and Bora Uçar. Fully-dynamic weighted matching approximation in practice. CoRR, abs/2104.13098, 2021. URL: http://arxiv.org/abs/2104.13098.
  17. Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc. Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, pages 7:1-7:16, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.7.
  18. Sabeur Aridhi, Martin Brugnara, Alberto Montresor, and Yannis Velegrakis. Distributed k-core decomposition and maintenance in large dynamic graphs. In Proc. of the 10th ACM International Conference on Distributed and Event-based Systems, pages 161-168, 2016. URL: https://doi.org/10.1145/2933267.2933299.
  19. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear update time. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proc. of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 815-826. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188922.
  20. Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear in n update time. In Timothy M. Chan, editor, Proc. of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1919-1936. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.116.
  21. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. Springer Science & Business Media, 2012. Google Scholar
  22. Muhammad A. Awad, Saman Ashkiani, Serban D. Porumbescu, and John D. Owens. Dynamic graphs on the GPU. In 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS), New Orleans, LA, USA, May 18-22, 2020, pages 739-748. IEEE, 2020. URL: https://doi.org/10.1109/IPDPS47924.2020.00081.
  23. Thomas Aynaud and Jean-Loup Guillaume. Static community detection algorithms for evolving networks. In Lavy Libman Ariel Orda, Nidhi Hegde, editor, 8th International Symposium on Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks (WiOpt 2010), May 31 - June 4, 2010, University of Avignon, Avignon, France, pages 513-519. IEEE, 2010. URL: http://ieeexplore.ieee.org/document/5520221/.
  24. Shweta Bansal, Sanjukta Bhowmick, and Prashant Paymal. Fast community detection for dynamic complex networks. In Luciano da F. Costa, Alexandre G. Evsukoff, Giuseppe Mangioni, and Ronaldo Menezes, editors, Complex Networks - Second International Workshop, CompleNet 2010, Rio de Janeiro, Brazil, October 13-15, 2010, Revised Selected Papers, volume 116 of Communications in Computer and Information Science, pages 196-207. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-25501-4_20.
  25. Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan. Dynamic DFS in undirected graphs: Breaking the o(m) barrier. SIAM J. Comput., 48(4):1335-1363, 2019. URL: https://doi.org/10.1137/17M114306X.
  26. Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in O(log n) update time. SIAM J. Comput., 44(1):88-113, 2015. URL: https://doi.org/10.1137/16M1106158.
  27. Surender Baswana, Shiv Kumar Gupta, and Ayush Tulsyan. Fault tolerant and fully dynamic DFS in undirected graphs: Simple yet efficient. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 65:1-65:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.65.
  28. Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner. Combining hierarchical and goal-directed speed-up techniques for dijkstra’s algorithm. ACM J. Exp. Algorithmics, 15, 2010. URL: https://doi.org/10.1145/1671970.1671976.
  29. Reinhard Bauer and Dorothea Wagner. Batch dynamic single-source shortest-path algorithms: An experimental study. In Jan Vahrenhold, editor, Experimental Algorithms, 8th International Symposium, SEA 2009, Dortmund, Germany, June 4-6, 2009. Proc., volume 5526 of Lecture Notes in Computer Science, pages 51-62. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02011-7_7.
  30. F. Becker. Generative Model for Dynamic Networks with Community Structures. Master’s Thesis, Heidelberg University, 2020. Google Scholar
  31. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 382-405. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00032.
  32. Richard Bellman. On a routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958. Google Scholar
  33. Elisabetta Bergamini and Henning Meyerhenke. Fully-dynamic approximation of betweenness centrality. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proc., volume 9294 of Lecture Notes in Computer Science, pages 155-166. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_14.
  34. Elisabetta Bergamini and Henning Meyerhenke. Approximating betweenness centrality in fully dynamic networks. Internet Math., 12(5):281-314, 2016. URL: https://doi.org/10.1080/15427951.2016.1177802.
  35. Elisabetta Bergamini, Henning Meyerhenke, and Christian Staudt. Approximating betweenness centrality in large evolving networks. In Ulrik Brandes and David Eppstein, editors, Proc. of the Seventeenth Workshop on Algorithm Engineering and Experiments, ALENEX 2015, San Diego, CA, USA, January 5, 2015, pages 133-146. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973754.12.
  36. Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. In Timothy M. Chan, editor, Proc. of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1899-1918. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.115.
  37. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Proc. of the 27th Symposium on Discrete Algorithms SODA, pages 692-711. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch50.
  38. Emanuele Berrettini, Gianlorenzo D'Angelo, and Daniel Delling. Arc-flags in dynamic graphs. In Jens Clausen and Gabriele Di Stefano, editors, ATMOS 2009 - 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, IT University of Copenhagen, Denmark, September 10, 2009, volume 12 of OASICS. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009. URL: http://drops.dagstuhl.de/opus/volltexte/2009/2149.
  39. Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. Deterministic dynamic matching in O(1) update time. Algorithmica, 82(4):1057-1080, 2020. URL: https://doi.org/10.1007/s00453-019-00630-4.
  40. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. SIAM J. Comput., 47(3):859-887, 2018. URL: https://doi.org/10.1137/140998925.
  41. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Dynamic algorithms via the primal-dual method. Inf. Comput., 261:219-239, 2018. URL: https://doi.org/10.1016/j.ic.2018.02.005.
  42. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In Proc. of the 48th Annual Symposium on Theory of Computing, pages 398-411. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897568.
  43. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. Fully dynamic approximate maximum matching and minimum vertex cover in O(log^3 n) worst case update time. In Philip N. Klein, editor, Proc. of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms SODA, pages 470-489. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611973730.54.
  44. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. A new deterministic algorithm for dynamic set cover. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 406-423. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00033.
  45. Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos E. Tsourakakis. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proc. of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 173-182. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746592.
  46. Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Xiaowei Wu. An improved algorithm for dynamic set cover. CoRR, abs/2002.11171, 2020. URL: http://arxiv.org/abs/2002.11171.
  47. Sayan Bhattacharya and Janardhan Kulkarni. Deterministically maintaining a (2 + ε)-approximate minimum vertex cover in o(1/ε²) amortized update time. In Timothy M. Chan, editor, Proc. of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1872-1885. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.113.
  48. Sujoy Bhore, Guangping Li, and Martin Nöllenburg. An algorithmic study of fully dynamic independent sets for map labeling. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 19:1-19:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.19.
  49. Patrick Bisenius, Elisabetta Bergamini, Eugenio Angriman, and Henning Meyerhenke. Computing top-k closeness centrality in fully-dynamic graphs. In Rasmus Pagh and Suresh Venkatasubramanian, editors, Proc. of the Twentieth Workshop on Algorithm Engineering and Experiments, ALENEX 2018, New Orleans, LA, USA, January 7-8, 2018, pages 21-35. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975055.3.
  50. Yuri Boykov and Vladimir Kolmogorov. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Mach. Intell., 26(9):1124-1137, 2004. URL: https://doi.org/10.1109/TPAMI.2004.60.
  51. U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner. On Modularity Clustering. IEEE Transactions on Knowledge and Data Engineering, 20(2):172-188, 2008. URL: https://doi.org/10.1109/TKDE.2007.190689.
  52. Valentin Buchhold, Daniel Delling, Dennis Schieferdecker, and Michael Wegner. Fast and stable repartitioning of road networks. In 18th International Symposium on Experimental Algorithms (SEA 2020), volume 160 of LIPIcs, pages 26:1-26:15. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.SEA.2020.26.
  53. Laurent Bulteau, Vincent Froese, Konstantin Kutzkov, and Rasmus Pagh. Triangle counting in dynamic graph streams. Algorithmica, 76(1):259-278, 2016. URL: https://doi.org/10.1007/s00453-015-0036-4.
  54. Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In Stijn Vansummeren, editor, Proc. of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, USA, pages 253-262. ACM, 2006. URL: https://doi.org/10.1145/1142351.1142388.
  55. Luciana S. Buriol, Mauricio G. C. Resende, and Mikkel Thorup. Speeding up dynamic shortest-path algorithms. INFORMS J. Comput., 20(2):191-204, 2008. URL: https://doi.org/10.1287/ijoc.1070.0231.
  56. Giuseppe Cattaneo, Pompeo Faruolo, Umberto Ferraro Petrillo, and Giuseppe F. Italiano. Maintaining dynamic minimum spanning trees: An experimental study. In David M. Mount and Clifford Stein, editors, Algorithm Engineering and Experiments, 4th International Workshop, ALENEX 2002, San Francisco, CA, USA, January 4-5, 2002, Revised Papers, volume 2409 of Lecture Notes in Computer Science, pages 111-125. Springer, 2002. URL: https://doi.org/10.1007/3-540-45643-0_9.
  57. Giuseppe Cattaneo, Pompeo Faruolo, Umberto Ferraro Petrillo, and Giuseppe F. Italiano. Maintaining dynamic minimum spanning trees: An experimental study. Discret. Appl. Math., 158(5):404-425, 2010. URL: https://doi.org/10.1016/j.dam.2009.10.005.
  58. Edward P. F. Chan and Yaya Yang. Shortest path tree computation in dynamic graphs. IEEE Trans. Computers, 58(4):541-557, 2009. URL: https://doi.org/10.1109/TC.2008.198.
  59. Moses Charikar and Shay Solomon. Fully dynamic almost-maximal matching: Breaking the polynomial worst-case time barrier. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, volume 107 of LIPIcs, pages 33:1-33:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.33.
  60. Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 370-381. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00031.
  61. Mostafa Haghir Chehreghani, Albert Bifet, and Talel Abdessalem. Dybed: An efficient algorithm for updating betweenness centrality in directed dynamic graphs. In Naoki Abe, Huan Liu, Calton Pu, Xiaohua Hu, Nesreen K. Ahmed, Mu Qiao, Yang Song, Donald Kossmann, Bing Liu, Kisung Lee, Jiliang Tang, Jingrui He, and Jeffrey S. Saltz, editors, IEEE International Conference on Big Data, Big Data 2018, Seattle, WA, USA, December 10-13, 2018, pages 2114-2123. IEEE, 2018. URL: https://doi.org/10.1109/BigData.2018.8622452.
  62. Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, and Thatchaphol Saranurak. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1135-1146. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00109.
  63. Pierluigi Crescenzi, Clémence Magnien, and Andrea Marino. Finding top-k nodes for temporal closeness in large temporal graphs. Algorithms, 13(9):211, 2020. URL: https://doi.org/10.3390/a13090211.
  64. Michael Crouch and Daniel S. Stubbs. Improved streaming algorithms for weighted matching, via unweighted matching. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, volume 28 of LIPIcs, pages 96-104. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.96.
  65. Annalisa D'Andrea, Mattia D'Emidio, Daniele Frigioni, Stefano Leucci, and Guido Proietti. Dynamic maintenance of a shortest-path tree on homogeneous batches of updates: New algorithms and experiments. ACM J. Exp. Algorithmics, 20:1.5:1.1-1.5:1.33, 2015. URL: https://doi.org/10.1145/2786022.
  66. Gianlorenzo D'Angelo, Mattia D'Emidio, and Daniele Frigioni. Fully dynamic update of arc-flags. Networks, 63(3):243-259, 2014. URL: https://doi.org/10.1002/net.21542.
  67. Gianlorenzo D'Angelo, Mattia D'Emidio, and Daniele Frigioni. Fully dynamic 2-hop cover labeling. ACM J. Exp. Algorithmics, 24(1):1.6:1-1.6:36, 2019. URL: https://doi.org/10.1145/3299901.
  68. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato Fonseca F. Werneck. Customizable route planning. In Panos M. Pardalos and Steffen Rebennack, editors, Experimental Algorithms - 10th International Symposium, SEA 2011, Kolimpari, Chania, Crete, Greece, May 5-7, 2011. Proc., volume 6630 of Lecture Notes in Computer Science, pages 376-387. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-20662-7_32.
  69. Daniel Delling and Dorothea Wagner. Landmark-based routing in dynamic graphs. In Camil Demetrescu, editor, Experimental Algorithms, 6th International Workshop, WEA 2007, Rome, Italy, June 6-8, 2007, Proc., volume 4525 of Lecture Notes in Computer Science, pages 52-65. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-72845-0_5.
  70. Camil Demetrescu. Fully Dynamic Algorithms for Path Problems on Directed Graphs. PhD thesis, Universtita Degli Studi Di Roma, 2001. URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.8921.
  71. Camil Demetrescu, Daniele Frigioni, Alberto Marchetti-Spaccamela, and Umberto Nanni. Maintaining shortest paths in digraphs with arbitrary arc weights: An experimental study. In Stefan Näher and Dorothea Wagner, editors, Algorithm Engineering, 4th International Workshop, WAE 2000, Saarbrücken, Germany, September 5-8, 2000, Proc., volume 1982 of Lecture Notes in Computer Science, pages 218-229. Springer, 2000. URL: https://doi.org/10.1007/3-540-44691-5_19.
  72. Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. J. ACM, 51(6):968-992, 2004. URL: https://doi.org/10.1145/1039488.1039492.
  73. Camil Demetrescu and Giuseppe F. Italiano. Experimental analysis of dynamic all pairs shortest path algorithms. ACM Trans. Algorithms, 2(4):578-601, 2006. URL: https://doi.org/10.1145/1198513.1198519.
  74. Laxman Dhulipala, Quanquan C. Liu, and Julian Shun. Parallel batch-dynamic k-clique counting. CoRR, abs/2003.13585, 2020. URL: http://arxiv.org/abs/2003.13585.
  75. Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959. URL: https://doi.org/10.1007/BF01386390.
  76. Christof Doll, Tanja Hartmann, and Dorothea Wagner. Fully-dynamic hierarchical graph clustering using cut trees. In 12th Intl. Symp. on Algorithms and Data Structures, WADS'11, volume 6844 of LNCS, pages 338-349, 2011. URL: https://doi.org/10.1007/978-3-642-22300-6_29.
  77. David Ediger, Robert McColl, E. Jason Riedy, and David A. Bader. STINGER: high performance data structure for streaming graphs. In IEEE Conference on High Performance Extreme Computing, HPEC 2012, Waltham, MA, USA, September 10-12, 2012, pages 1-5. IEEE, 2012. URL: https://doi.org/10.1109/HPEC.2012.6408680.
  78. Jack R. Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM, 19(2):248-264, 1972. URL: https://doi.org/10.1145/321694.321699.
  79. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator based sparsification. i. planary testing and minimum spanning trees. J. Comput. Syst. Sci., 52(1):3-27, 1996. URL: https://doi.org/10.1006/jcss.1996.0002.
  80. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator-based sparsification II: edge and vertex connectivity. SIAM J. Comput., 28(1):341-381, 1998. URL: https://doi.org/10.1137/S0097539794269072.
  81. David Eppstein, Michael T. Goodrich, Darren Strash, and Lowell Trott. Extended dynamic subgraph statistics using h-index parameterized data structures. Theor. Comput. Sci., 447:44-52, 2012. URL: https://doi.org/10.1016/j.tcs.2011.11.034.
  82. David Eppstein and Emma S. Spiro. The h-index of a graph and its application to dynamic subgraph statistics. J. Graph Algorithms Appl., 16(2):543-567, 2012. URL: https://doi.org/10.7155/jgaa.00273.
  83. Wenfei Fan, Muyang Liu, Chao Tian, Ruiqi Xu, and Jingren Zhou. Incrementalization of graph partitioning algorithms. Proc. VLDB Endow., 13(8):1261-1274, 2020. URL: https://doi.org/10.14778/3389133.3389142.
  84. Guoyao Feng, Xiao Meng, and Khaled Ammar. Distinger: A distributed graph data structure for massive dynamic graph processing. In 2015 IEEE International Conference on Big Data (Big Data), pages 1814-1822. IEEE, 2015. URL: https://doi.org/10.1109/BigData.2015.7363954.
  85. Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput., 14(4):781-798, 1985. URL: https://doi.org/10.1137/0214055.
  86. Greg N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput., 26(2):484-538, 1997. URL: https://doi.org/10.1137/S0097539792226825.
  87. Daniele Frigioni, Mario Ioffreda, Umberto Nanni, and Giulio Pasqualone. Experimental analysis of dynamic algorithms for the single-source shortest-path problem. ACM J. Exp. Algorithmics, 3:5, 1998. URL: https://doi.org/10.1145/297096.297147.
  88. Daniele Frigioni, Alberto Marchetti-Spaccamela, and Umberto Nanni. Fully dynamic output bounded single source shortest path problem (extended abstract). In Éva Tardos, editor, Proc. of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 28-30 January 1996, Atlanta, Georgia, USA, pages 212-221. ACM/SIAM, 1996. URL: http://dl.acm.org/citation.cfm?id=313852.313926.
  89. Daniele Frigioni, Tobias Miller, Umberto Nanni, and Christos D. Zaroliagis. An experimental study of dynamic algorithms for transitive closure. ACM J. Exp. Algorithmics, 6:9, 2001. URL: https://doi.org/10.1145/945394.945403.
  90. Andrew V. Goldberg and Chris Harrelson. Computing the shortest path: A search meets graph theory. In Proc. of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 156-165. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070455.
  91. Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Pushmeet Kohli, Robert Endre Tarjan, and Renato F. Werneck. Faster and more dynamic maximum flow by incremental breadth-first search. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proc., volume 9294 of Lecture Notes in Computer Science, pages 619-630. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_52.
  92. Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, 1988. Google Scholar
  93. Andrew V. Goldberg and Robert Endre Tarjan. A new approach to the maximum-flow problem. J. ACM, 35(4):921-940, 1988. URL: https://doi.org/10.1145/48014.61051.
  94. Gramoz Goranci, Monika Henzinger, and Mikkel Thorup. Incremental exact min-cut in polylogarithmic amortized update time. ACM Transactions on Algorithms (TALG), 14(2):1-21, 2018. Google Scholar
  95. Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan. The expander hierarchy and its applications to dynamic graph algorithms. CoRR, abs/2005.02369, 2020. URL: http://arxiv.org/abs/2005.02369.
  96. Robert Görke, Tanja Hartmann, and Dorothea Wagner. Dynamic graph clustering using minimum-cut trees. J. Graph Algorithms Appl., 16(2):411-446, 2012. URL: https://doi.org/10.7155/jgaa.00269.
  97. Robert Görke, Roland Kluge, Andrea Schumm, Christian Staudt, and Dorothea Wagner. An efficient generator for clustered dynamic random networks. In Guy Even and Dror Rawitz, editors, Design and Analysis of Algorithms - First Mediterranean Conference on Algorithms, MedAlg 2012, Kibbutz Ein Gedi, Israel, December 3-5, 2012. Proc., volume 7659 of Lecture Notes in Computer Science, pages 219-233. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-34862-4_16.
  98. Robert Görke, Pascal Maillard, Andrea Schumm, Christian Staudt, and Dorothea Wagner. Dynamic graph clustering combining modularity and smoothness. ACM J. Exp. Algorithmics, 18, 2013. URL: https://doi.org/10.1145/2444016.2444021.
  99. Robert Görke, Pascal Maillard, Christian Staudt, and Dorothea Wagner. Modularity-driven clustering of dynamic graphs. In Paola Festa, editor, Experimental Algorithms, 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proc., volume 6049 of Lecture Notes in Computer Science, pages 436-448. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13193-6_37.
  100. Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, and Shay Solomon. (1 + ε)-approximate incremental matching in constant deterministic amortized time. In Timothy M. Chan, editor, Proc. of the 20th Symposium on Discrete Algorithms, pages 1886-1898. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.114.
  101. Sergio Greco, Cristian Molinaro, Chiara Pulice, and Ximena Quintana. Incremental maximum flow computation on evolving networks. In Ahmed Seffah, Birgit Penzenstadler, Carina Alves, and Xin Peng, editors, Proc. of the Symposium on Applied Computing, SAC 2017, Marrakech, Morocco, April 3-7, 2017, pages 1061-1067. ACM, 2017. URL: https://doi.org/10.1145/3019612.3019816.
  102. Oded Green, Robert McColl, and David A. Bader. A fast algorithm for streaming betweenness centrality. In 2012 International Conference on Privacy, Security, Risk and Trust, PASSAT 2012, and 2012 International Confernece on Social Computing, SocialCom 2012, Amsterdam, Netherlands, September 3-5, 2012, pages 11-20. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/SocialCom-PASSAT.2012.37.
  103. Manoj Gupta and Shahbaz Khan. Simple dynamic algorithms for maximal independent set and other problems. In 4th Symposium on Simplicity in Algorithms, SOSA@SODA 2021, to appear, 2021. URL: http://arxiv.org/abs/1804.01823.
  104. Manoj Gupta and Richard Peng. Fully dynamic (1+ e)-approximate matchings. In 54th Symposium on Foundations of Computer Science, FOCS, pages 548-557. IEEE Computer Society, 2013. URL: https://ieeexplore.ieee.org/xpl/conhome/6685222/proceeding.
  105. Manoj Gupta and Richard Peng. Fully dynamic (1+ e)-approximate matchings. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 548-557. IEEE Computer Society, 2013. Google Scholar
  106. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Fully-dynamic all-pairs shortest paths: Improved worst-case time and space bounds. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2562-2574. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.156.
  107. Guyue Han and Harish Sethu. Edge sample and discard: A new algorithm for counting triangles in large dynamic graphs. In Jana Diesner, Elena Ferrari, and Guandong Xu, editors, Proc. of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, Sydney, Australia, July 31 - August 03, 2017, pages 44-49. ACM, 2017. URL: https://doi.org/10.1145/3110025.3110061.
  108. Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua. Fully dynamic four-vertex subgraph counting. CoRR, abs/2106.15524, 2021. URL: http://arxiv.org/abs/2106.15524.
  109. Kathrin Hanauer, Monika Henzinger, and Christian Schulz. Faster fully dynamic transitive closure in practice. In Simone Faro and Domenico Cantone, editors, 18th International Symposium on Experimental Algorithms, SEA 2020, June 16-18, 2020, Catania, Italy, volume 160 of LIPIcs, pages 14:1-14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.SEA.2020.14.
  110. Kathrin Hanauer, Monika Henzinger, and Christian Schulz. Fully dynamic single-source reachability in practice: An experimental study. In Guy E. Blelloch and Irene Finocchi, editors, Proc. of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020, Salt Lake City, UT, USA, January 5-6, 2020, pages 106-119. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611976007.9.
  111. Takanori Hayashi, Takuya Akiba, and Ken-ichi Kawarabayashi. Fully dynamic shortest-path distance query acceleration on massive networks. In Snehasis Mukhopadhyay, ChengXiang Zhai, Elisa Bertino, Fabio Crestani, Javed Mostafa, Jie Tang, Luo Si, Xiaofang Zhou, Yi Chang, Yunyao Li, and Parikshit Sondhi, editors, Proc. of the 25th ACM International Conference on Information and Knowledge Management, CIKM 2016, Indianapolis, IN, USA, October 24-28, 2016, pages 1533-1542. ACM, 2016. URL: https://doi.org/10.1145/2983323.2983731.
  112. Takanori Hayashi, Takuya Akiba, and Yuichi Yoshida. Fully dynamic betweenness centrality maintenance on massive networks. Proc. VLDB Endow., 9(2):48-59, 2015. URL: https://doi.org/10.14778/2850578.2850580.
  113. Keith Henderson and Tina Eliassi-Rad. Applying latent dirichlet allocation to group discovery in large graphs. In Sung Y. Shin and Sascha Ossowski, editors, Proc. of the 2009 ACM Symposium on Applied Computing (SAC), Honolulu, Hawaii, USA, March 9-12, 2009, pages 1456-1461. ACM, 2009. URL: https://doi.org/10.1145/1529282.1529607.
  114. Bruce Hendrickson, Robert W. Leland, and Rafael Van Driessche. Enhancing data locality by using terminal propagation. In 29th Annual Hawaii International Conference on System Sciences (HICSS-29), January 3-6, 1996, Maui, Hawaii, USA, pages 565-574. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/HICSS.1996.495507.
  115. Monika Henzinger. The state of the art in dynamic graph algorithms. In 44th Intl. Conf. on Current Trends in Theory and Practice of Computer Science, SOFSEM'18, volume 10706 of LNCS, pages 40-44. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-73117-9_3.
  116. Monika Henzinger, Shahbaz Khan, Richard Paul, and Christian Schulz. Dynamic matching algorithms in practice. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 58:1-58:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.58.
  117. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proc. of the forty-seventh annual ACM symposium on Theory of computing, pages 21-30, 2015. URL: https://doi.org/10.1145/2746539.2746609.
  118. Monika Henzinger, Alexander Noe, and Christian Schulz. Practical fully dynamic minimum cut algorithms. CoRR, abs/2101.05033, 2021. URL: http://arxiv.org/abs/2101.05033.
  119. Monika R Henzinger and Valerie King. Maintaining minimum spanning trees in dynamic graphs. In International Colloquium on Automata, Languages, and Programming, pages 594-604. Springer, 1997. Google Scholar
  120. Monika Rauch Henzinger. Approximating minimum cuts under insertions. In International Colloquium on Automata, Languages, and Programming, pages 280-291. Springer, 1995. Google Scholar
  121. Monika Rauch Henzinger. Fully dynamic biconnectivity in graphs. Algorithmica, 13(6):503-538, 1995. URL: https://doi.org/10.1007/BF01189067.
  122. Monika Rauch Henzinger. Improved data structures for fully dynamic biconnectivity. SIAM J. Comput., 29(6):1761-1815, 2000. URL: https://doi.org/10.1137/S0097539794263907.
  123. Monika Rauch Henzinger and Michael L. Fredman. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica, 22(3):351-362, 1998. URL: https://doi.org/10.1007/PL00009228.
  124. Monika Rauch Henzinger and Valerie King. Randomized dynamic graph algorithms with polylogarithmic time per operation. In Frank Thomson Leighton and Allan Borodin, editors, Proc. of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA, pages 519-527. ACM, 1995. URL: https://doi.org/10.1145/225058.225269.
  125. Monika Rauch Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM, 46(4):502-516, 1999. URL: https://doi.org/10.1145/320211.320215.
  126. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. In Jeffrey Scott Vitter, editor, Proc. of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 79-89. ACM, 1998. URL: https://doi.org/10.1145/276698.276715.
  127. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. URL: https://doi.org/10.1145/502090.502095.
  128. Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Faster fully-dynamic minimum spanning forest. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proc., volume 9294 of Lecture Notes in Computer Science, pages 742-753. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_62.
  129. Y.F. Hu and R.J. Blake. An improved diffusion algorithm for dynamic load balancing. Parallel Computing, 25(4):417-444, 1999. URL: https://doi.org/10.1016/S0167-8191(99)00002-2.
  130. Qiang-Sheng Hua, Yuliang Shi, Dongxiao Yu, Hai Jin, Jiguo Yu, Zhipeng Cai, Xiuzhen Cheng, and Hanhua Chen. Faster parallel core maintenance algorithms in dynamic graphs. IEEE Trans. Parallel Distributed Syst., 31(6):1287-1300, 2020. URL: https://doi.org/10.1109/TPDS.2019.2960226.
  131. Jiewen Huang and Daniel Abadi. LEOPARD: lightweight edge-oriented partitioning and replication for dynamic graphs. Proc. VLDB Endow., 9(7):540-551, 2016. URL: https://doi.org/10.14778/2904483.2904486.
  132. Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie. Fully dynamic connectivity in O(log n(log log n)^2) amortized expected time. In Philip N. Klein, editor, Proc. of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 510-520. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.32.
  133. Giuseppe Amato II, Giuseppe Cattaneo, and Giuseppe F. Italiano. Experimental analysis of dynamic minimum spanning tree algorithms (extended abstract). In Michael E. Saks, editor, Proc. of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana, USA, pages 314-323. ACM/SIAM, 1997. URL: http://dl.acm.org/citation.cfm?id=314161.314314.
  134. Giuseppe F. Italiano. Fully dynamic higher connectivity. In Encyclopedia of Algorithms, pages 797-800. Springer, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_154.
  135. Zoran Ivkovic and Errol L. Lloyd. Fully dynamic maintenance of vertex cover. In 19th International Workshop Graph-Theoretic Concepts in Computer Science, volume 790 of LNCS, pages 99-111, 1993. Google Scholar
  136. Keita Iwabuchi, Scott Sallinen, Roger Pearce, Brian Van Essen, Maya Gokhale, and Satoshi Matsuoka. Towards a distributed large-scale dynamic graph data store. In 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 892-901. IEEE, 2016. URL: https://doi.org/10.1109/IPDPSW.2016.189.
  137. Raj Iyer, David R. Karger, Hariharan Rahul, and Mikkel Thorup. An experimental study of polylogarithmic, fully dynamic, connectivity algorithms. ACM J. Exp. Algorithmics, 6:4, 2001. URL: https://doi.org/10.1145/945394.945398.
  138. Hai Jin, Na Wang, Dongxiao Yu, Qiang-Sheng Hua, Xuanhua Shi, and Xia Xie. Core maintenance in dynamic graphs: A parallel approach based on matching. IEEE Trans. Parallel Distributed Syst., 29(11):2416-2428, 2018. URL: https://doi.org/10.1109/TPDS.2018.2835441.
  139. Wenyu Jin and Xiaorui Sun. Fully dynamic c-edge connectivity in subpolynomial time. CoRR, abs/2004.07650, 2020. URL: http://arxiv.org/abs/2004.07650.
  140. Hossein Jowhari and Mohammad Ghodsi. New streaming algorithms for counting triangles in graphs. In Lusheng Wang, editor, Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proc., volume 3595 of Lecture Notes in Computer Science, pages 710-716. Springer, 2005. URL: https://doi.org/10.1007/11533719_72.
  141. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Sanjeev Khanna, editor, Proc. of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1131-1142. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.81.
  142. Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Counting triangles under updates in worst-case optimal time. In Pablo Barceló and Marco Calautti, editors, 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, volume 127 of LIPIcs, pages 4:1-4:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICDT.2019.4.
  143. Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Maintaining triangle queries under updates. ACM Trans. Database Syst., 45(3):11:1-11:46, 2020. URL: https://doi.org/10.1145/3396375.
  144. Miray Kas, Kathleen M. Carley, and L. Richard Carley. Incremental closeness centrality for dynamically changing social networks. In Jon G. Rokne and Christos Faloutsos, editors, Advances in Social Networks Analysis and Mining 2013, ASONAM '13, Niagara, ON, Canada - August 25 - 29, 2013, pages 1250-1258. ACM, 2013. URL: https://doi.org/10.1145/2492517.2500270.
  145. Shahbaz Khan. Near optimal parallel algorithms for dynamic DFS in undirected graphs. ACM Trans. Parallel Comput., 6(3):18:1-18:33, 2019. URL: https://doi.org/10.1145/3364212.
  146. Tim Kiefer, Dirk Habich, and Wolfgang Lehner. Penalized graph partitioning for static and dynamic load balancing. In Pierre-François Dutot and Denis Trystram, editors, Euro-Par 2016: Parallel Processing - 22nd International Conference on Parallel and Distributed Computing, Grenoble, France, August 24-26, 2016, Proc., volume 9833 of Lecture Notes in Computer Science, pages 146-158. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-43659-3_11.
  147. Valerie King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 81-91. IEEE Computer Society, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814580.
  148. Valerie King and Mikkel Thorup. A space saving trick for directed dynamic transitive closure and shortest path algorithms. In Jie Wang, editor, Computing and Combinatorics, 7th Annual International Conference, COCOON 2001, Guilin, China, August 20-23, 2001, Proc., volume 2108 of Lecture Notes in Computer Science, pages 268-277. Springer, 2001. URL: https://doi.org/10.1007/3-540-44679-6_30.
  149. Pushmeet Kohli and Philip H. S. Torr. Dynamic graph cuts for efficient inference in markov random fields. IEEE Trans. Pattern Anal. Mach. Intell., 29(12):2079-2088, 2007. URL: https://doi.org/10.1109/TPAMI.2007.1128.
  150. Pushmeet Kohli and Philip H. S. Torr. Dynamic graph cuts and their applications in computer vision. In Roberto Cipolla, Sebastiano Battiato, and Giovanni Maria Farinella, editors, Computer Vision: Detection, Recognition and Reconstruction, volume 285 of Studies in Computational Intelligence, pages 51-108. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-12848-6_3.
  151. Nicolas Kourtellis, Gianmarco De Francisci Morales, and Francesco Bonchi. Scalable online betweenness centrality in evolving graphs. IEEE Trans. Knowl. Data Eng., 27(9):2494-2506, 2015. URL: https://doi.org/10.1109/TKDE.2015.2419666.
  152. Nicolas Kourtellis, Gianmarco De Francisci Morales, and Francesco Bonchi. Scalable online betweenness centrality in evolving graphs. In 32nd IEEE International Conference on Data Engineering, ICDE 2016, Helsinki, Finland, May 16-20, 2016, pages 1580-1581. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/ICDE.2016.7498421.
  153. Ioannis Krommidas and Christos D. Zaroliagis. An experimental study of algorithms for fully dynamic transitive closure. ACM J. Exp. Algorithmics, 12:1.6:1-1.6:22, 2008. URL: https://doi.org/10.1145/1227161.1370597.
  154. S. Kumar and P. Gupta. An incremental algorithm for the maximum flow problem. J. Math. Model. Algorithms, 2(1):1-16, 2003. URL: https://doi.org/10.1023/A:1023607406540.
  155. Min-Joong Lee, Sunghee Choi, and Chin-Wan Chung. Efficient algorithms for updating betweenness centrality in fully dynamic graphs. Inf. Sci., 326:278-296, 2016. URL: https://doi.org/10.1016/j.ins.2015.07.053.
  156. Min-Joong Lee, Jungmin Lee, Jaimie Yejean Park, Ryan Hyun Choi, and Chin-Wan Chung. QUBE: a quick algorithm for updating betweenness centrality. In Alain Mille, Fabien L. Gandon, Jacques Misselis, Michael Rabinovich, and Steffen Staab, editors, Proc. of the 21st World Wide Web Conference 2012, WWW 2012, Lyon, France, April 16-20, 2012, pages 351-360. ACM, 2012. URL: https://doi.org/10.1145/2187836.2187884.
  157. Rong-Hua Li, Jeffrey Xu Yu, and Rui Mao. Efficient core maintenance in large dynamic graphs. IEEE Trans. Knowl. Data Eng., 26(10):2453-2465, 2014. URL: https://doi.org/10.1109/TKDE.2013.158.
  158. Yongsub Lim, Minsoo Jung, and U Kang. Memory-efficient and accurate sampling for counting local triangles in graph streams: From simple to multigraphs. ACM Trans. Knowl. Discov. Data, 12(1):4:1-4:28, 2018. URL: https://doi.org/10.1145/3022186.
  159. Yongsub Lim and U Kang. MASCOT: memory-efficient and accurate sampling for counting local triangles in graph streams. In Longbing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I. Webb, Dragos D. Margineantu, and Graham Williams, editors, Proc. of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, pages 685-694. ACM, 2015. URL: https://doi.org/10.1145/2783258.2783285.
  160. Paul Liu, Austin R. Benson, and Moses Charikar. Sampling methods for counting temporal motifs. In J. Shane Culpepper, Alistair Moffat, Paul N. Bennett, and Kristina Lerman, editors, Proc. of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM 2019, Melbourne, VIC, Australia, February 11-15, 2019, pages 294-302. ACM, 2019. URL: https://doi.org/10.1145/3289600.3290988.
  161. Shangqi Lu and Yufei Tao. Towards optimal dynamic indexes for approximate (and exact) triangle counting. In Ke Yi and Zhewei Wei, editors, 24th International Conference on Database Theory, ICDT 2021, March 23-26, 2021, Nicosia, Cyprus, volume 186 of LIPIcs, pages 6:1-6:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICDT.2021.6.
  162. Amgad Madkour, Walid G Aref, Faizan Ur Rehman, Mohamed Abdur Rahman, and Saleh Basalamah. A survey of shortest-path algorithms. arXiv preprint, 2017. URL: http://arxiv.org/abs/1705.02044.
  163. Devavret Makkar, David A. Bader, and Oded Green. Exact and parallel triangle counting in dynamic graphs. In 24th IEEE International Conference on High Performance Computing, HiPC 2017, Jaipur, India, December 18-21, 2017, pages 2-12. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/HiPC.2017.00011.
  164. Alberto Marchetti-Spaccamela, Umberto Nanni, and Hans Rohnert. Maintaining a topological order under edge insertions. Inf. Process. Lett., 59(1):53-58, 1996. URL: https://doi.org/10.1016/0020-0190(96)00075-0.
  165. Henning Meyerhenke. Dynamic load balancing for parallel numerical simulations based on repartitioning with disturbed diffusion. In 15th International Conference on Parallel and Distributed Systems, pages 150-157. IEEE, 2009. URL: https://doi.org/10.1109/ICPADS.2009.114.
  166. Henning Meyerhenke and Joachim Gehweiler. On dynamic graph partitioning and graph clustering using diffusion. In Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, and Peter Sanders, editors, Algorithm Engineering, 27.06. - 02.07.2010, volume 10261 of Dagstuhl Seminar Proc. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2010. URL: http://drops.dagstuhl.de/opus/volltexte/2010/2798/.
  167. Kurt T Miller and Tina Eliassi-Rad. Continuous time group discovery in dynamic graphs. In Notes of the 2009 NIPS Workshop on Analyzing Networks and Learning with Graphs, Whistler, BC, Canada, 2009. Google Scholar
  168. Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, and Roberto Tamassia. Complexity models for incremental computation. Theor. Comput. Sci., 130(1):203-236, 1994. URL: https://doi.org/10.1016/0304-3975(94)90159-7.
  169. Daniele Miorandi and Francesco De Pellegrini. K-shell decomposition for dynamic complex networks. In Lavy Libman Ariel Orda, Nidhi Hegde, editor, 8th International Symposium on Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks (WiOpt 2010), May 31 - June 4, 2010, University of Avignon, Avignon, France, pages 488-496. IEEE, 2010. URL: http://ieeexplore.ieee.org/document/5520231/.
  170. Sudip Misra and B. John Oommen. Dynamic algorithms for the shortest path routing problem: Learning automata-based solutions. IEEE Trans. Syst. Man Cybern. Part B, 35(6):1179-1192, 2005. URL: https://doi.org/10.1109/TSMCB.2005.850180.
  171. Kingshuk Mukherjee, Md Mahmudul Hasan, Christina Boucher, and Tamer Kahveci. Counting motifs in dynamic networks. BMC Syst. Biol., 12(1):1-12, 2018. URL: https://doi.org/10.1186/s12918-018-0533-6.
  172. Kengo Nakamura and Kunihiko Sadakane. Space-efficient fully dynamic DFS in undirected graphs. Algorithms, 12(3):52, 2019. URL: https://doi.org/10.3390/a12030052.
  173. Paolo Narváez, Kai-Yeung Siu, and Hong-Yi Tzeng. New dynamic algorithms for shortest path tree computation. IEEE/ACM Trans. Netw., 8(6):734-746, 2000. URL: https://doi.org/10.1109/90.893870.
  174. Paolo Narváez, Kai-Yeung Siu, and Hong-Yi Tzeng. New dynamic SPT algorithm based on a ball-and-string model. IEEE/ACM Trans. Netw., 9(6):706-718, 2001. URL: https://doi.org/10.1109/90.974525.
  175. Meghana Nasre, Matteo Pontecorvi, and Vijaya Ramachandran. Betweenness centrality - incremental and faster. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, volume 8635 of Lecture Notes in Computer Science, pages 577-588. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44465-8_49.
  176. Eisha Nathan and David A. Bader. Approximating personalized katz centrality in dynamic graphs. In Roman Wyrzykowski, Jack J. Dongarra, Ewa Deelman, and Konrad Karczewski, editors, Parallel Processing and Applied Mathematics - 12th International Conference, PPAM 2017, Lublin, Poland, September 10-13, 2017, Revised Selected Papers, Part I, volume 10777 of Lecture Notes in Computer Science, pages 290-302. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-78024-5_26.
  177. Eisha Nathan and David A. Bader. A dynamic algorithm for updating katz centrality in graphs. In Jana Diesner, Elena Ferrari, and Guandong Xu, editors, Proc. of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, Sydney, Australia, July 31 - August 03, 2017, pages 149-154. ACM, 2017. URL: https://doi.org/10.1145/3110025.3110034.
  178. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. ACM Trans. Algorithms, 12(1):7:1-7:15, 2016. URL: https://doi.org/10.1145/2700206.
  179. M. EJ Newman and M. Girvan. Finding and Evaluating Community Structure in Networks. Physical review E, 69(2):026113, 2004. URL: https://doi.org/10.1103/PhysRevE.69.026113.
  180. Daniel Nicoara, Shahin Kamali, Khuzaima Daudjee, and Lei Chen. Hermes: Dynamic partitioning for distributed social network graph databases. In EDBT, pages 25-36, 2015. URL: https://doi.org/10.5441/002/edbt.2015.04.
  181. Krzysztof Onak and Ronitt Rubinfeld. Maintaining a large matching and a small vertex cover. In STOC, pages 457-464, 2010. URL: https://doi.org/10.1145/1806689.1806753.
  182. James B. Orlin. Max flows in o(nm) time, or better. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 765-774. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488705.
  183. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Proc. of the 42nd ACM Symposium on Theory of Computing, STOC, pages 603-610. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806772.
  184. Mihai Patrascu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput., 35(4):932-963, 2006. URL: https://doi.org/10.1137/S0097539705447256.
  185. A. Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Counting and sampling triangles from a graph stream. Proc. VLDB Endow., 6(14):1870-1881, 2013. URL: https://doi.org/10.14778/2556549.2556569.
  186. D. Pearce and P. Kelly. A batch algorithm for maintaining a topological order. In ACSC, 2010. URL: https://doi.org/10.5555/1862199.1862208.
  187. David J. Pearce and Paul H. J. Kelly. A dynamic algorithm for topologically sorting directed acyclic graphs. In Celso C. Ribeiro and Simone L. Martins, editors, Experimental and Efficient Algorithms, Third International Workshop, WEA 2004, Angra dos Reis, Brazil, May 25-28, 2004, Proc., volume 3059 of Lecture Notes in Computer Science, pages 383-398. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-24838-5_29.
  188. David J. Pearce and Paul H. J. Kelly. A dynamic topological sort algorithm for directed acyclic graphs. ACM J. Exp. Algorithmics, 11, 2006. URL: https://doi.org/10.1145/1187436.1210590.
  189. David J. Pearce, Paul H. J. Kelly, and Chris Hankin. Online cycle detection and difference propagation: Applications to pointer analysis. Softw. Qual. J., 12(4):311-337, 2004. URL: https://doi.org/10.1023/B:SQJO.0000039791.93071.a2.
  190. Reynaldo Gil Pons. Space efficient incremental betweenness algorithm for directed graphs. In Rubén Vera-Rodríguez, Julian Fiérrez, and Aythami Morales, editors, Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications - 23rd Iberoamerican Congress, CIARP 2018, Madrid, Spain, November 19-22, 2018, Proc., volume 11401 of Lecture Notes in Computer Science, pages 262-270. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-13469-3_31.
  191. Matteo Pontecorvi and Vijaya Ramachandran. Fully dynamic betweenness centrality. In Khaled M. Elbassioni and Kazuhisa Makino, editors, Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, volume 9472 of Lecture Notes in Computer Science, pages 331-342. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48971-0_29.
  192. K. (Lynn) Putman, Hanjo D. Boekhout, and Frank W. Takes. Fast incremental computation of harmonic closeness centrality in directed weighted networks. In Francesca Spezzano, Wei Chen, and Xiaokui Xiao, editors, ASONAM '19: International Conference on Advances in Social Networks Analysis and Mining, Vancouver, British Columbia, Canada, 27-30 August, 2019, pages 1018-1025. ACM, 2019. URL: https://doi.org/10.1145/3341161.3344829.
  193. G Ramalingam and Thomas Reps. On the computational complexity of incremental algorithms. Technical report, University of Wisconsin-Madison Department of Computer Sciences, 1991. Google Scholar
  194. G. Ramalingam and Thomas W. Reps. An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms, 21(2):267-305, 1996. URL: https://doi.org/10.1006/jagm.1996.0046.
  195. G. Ramalingam and Thomas W. Reps. On the computational complexity of dynamic graph problems. Theor. Comput. Sci., 158(1&2):233-277, 1996. URL: https://doi.org/10.1016/0304-3975(95)00079-8.
  196. Celso C. Ribeiro and Rodrigo F. Toso. Experimental analysis of algorithms for updating minimum spanning trees on graphs subject to changes on edge weights. In Camil Demetrescu, editor, Experimental Algorithms, 6th International Workshop, WEA 2007, Rome, Italy, June 6-8, 2007, Proc., volume 4525 of Lecture Notes in Computer Science, pages 393-405. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-72845-0_30.
  197. Matteo Riondato and Evgenios M. Kornaropoulos. Fast approximation of betweenness centrality through sampling. In Ben Carterette, Fernando Diaz, Carlos Castillo, and Donald Metzler, editors, Seventh ACM International Conference on Web Search and Data Mining, WSDM 2014, New York, NY, USA, February 24-28, 2014, pages 413-422. ACM, 2014. URL: https://doi.org/10.1145/2556195.2556224.
  198. Liam Roditty. A faster and simpler fully dynamic transitive closure. ACM Trans. Algorithms, 4(1):6:1-6:16, 2008. URL: https://doi.org/10.1145/1328911.1328917.
  199. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389-401, 2011. URL: https://doi.org/10.1007/s00453-010-9401-5.
  200. Liam Roditty and Uri Zwick. Dynamic approximate all-pairs shortest paths in undirected graphs. SIAM J. Comput., 41(3):670-683, 2012. URL: https://doi.org/10.1137/090776573.
  201. Liam Roditty and Uri Zwick. A fully dynamic reachability algorithm for directed graphs with an almost linear update time. SIAM Journal on Computing, 45(3):712-733, 2016. URL: https://doi.org/10.1137/13093618X.
  202. Giulio Rossetti and Rémy Cazabet. Community discovery in dynamic networks: A survey. ACM Comput. Surv., 51(2):35:1-35:37, 2018. URL: https://doi.org/10.1145/3172867.
  203. Tiberiu Rotaru and Hans-Heinrich Nägeli. Dynamic load balancing by diffusion in heterogeneous systems. Journal of Parallel and Distributed Computing, 64(4):481-497, 2004. URL: https://doi.org/10.1016/j.jpdc.2004.02.001.
  204. Chayma Sakouhi, Sabeur Aridhi, Alessio Guerrieri, Salma Sassi, and Alberto Montresor. Dynamicdfep: A distributed edge partitioning approach for large dynamic graphs. In Evan Desai, Bipin C. Desai, Motomichi Toyama, and Jorge Bernardino, editors, Proc. of the 20th International Database Engineering & Applications Symposium, IDEAS 2016, Montreal, QC, Canada, July 11-13, 2016, pages 142-147. ACM, 2016. URL: https://doi.org/10.1145/2938503.2938506.
  205. Piotr Sankowski. Dynamic transitive closure via dynamic matrix inverse (extended abstract). In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proc., pages 509-517. IEEE Computer Society, 2004. URL: https://doi.org/10.1109/FOCS.2004.25.
  206. Piotr Sankowski. Subquadratic algorithm for dynamic shortest distances. In Lusheng Wang, editor, Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, volume 3595 of Lecture Notes in Computer Science, pages 461-470. Springer, 2005. URL: https://doi.org/10.1007/11533719_47.
  207. Piotr Sankowski. Faster dynamic matchings and vertex connectivity. In SODA, pages 118-126, 2007. URL: https://doi.org/10.1145/1283383.1283397.
  208. Ahmet Erdem Sariyüce, Bugra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, and Ümit V. Çatalyürek. Incremental k-core decomposition: algorithms and evaluation. VLDB J., 25(3):425-447, 2016. URL: https://doi.org/10.1007/s00778-016-0423-8.
  209. Ahmet Erdem Sariyüce, Kamer Kaya, Erik Saule, and Ümit V. Çatalyürek. Incremental algorithms for closeness centrality. In Xiaohua Hu, Tsau Young Lin, Vijay V. Raghavan, Benjamin W. Wah, Ricardo Baeza-Yates, Geoffrey C. Fox, Cyrus Shahabi, Matthew Smith, Qiang Yang, Rayid Ghani, Wei Fan, Ronny Lempel, and Raghunath Nambiar, editors, Proc. of the 2013 IEEE International Conference on Big Data, 6-9 October 2013, Santa Clara, CA, USA, pages 487-492. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/BigData.2013.6691611.
  210. Ahmet Erdem Sariyüce, Erik Saule, Kamer Kaya, and Ümit V. Çatalyürek. STREAMER: A distributed framework for incremental closeness centrality computation. In 2013 IEEE International Conference on Cluster Computing, CLUSTER 2013, Indianapolis, IN, USA, September 23-27, 2013, pages 1-8. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/CLUSTER.2013.6702680.
  211. Ahmet Erdem Sariyüce, Erik Saule, Kamer Kaya, and Ümit V. Çatalyürek. Incremental closeness centrality in distributed memory. Parallel Comput., 47:3-18, 2015. URL: https://doi.org/10.1016/j.parco.2015.01.003.
  212. Benjamin Schiller, Sven Jager, Kay Hamacher, and Thorsten Strufe. Stream - A stream-based algorithm for counting motifs in dynamic graphs. In Adrian-Horia Dediu, Francisco Hernández Quiroz, Carlos Martín-Vide, and David A. Rosenblueth, editors, Algorithms for Computational Biology - Second International Conference, AlCoB 2015, Mexico City, Mexico, August 4-5, 2015, Proc., volume 9199 of Lecture Notes in Computer Science, pages 53-67. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21233-3_5.
  213. Kirk Schloegel, George Karypis, and Vipin Kumar. Multilevel diffusion schemes for repartitioning of adaptive meshes. J. Parallel Distributed Comput., 47(2):109-124, 1997. URL: https://doi.org/10.1006/jpdc.1997.1410.
  214. Kirk Schloegel, George Karypis, and Vipin Kumar. A unified algorithm for load-balancing adaptive scientific simulations. In Jed Donnelley, editor, Proc. Supercomputing 2000, November 4-10, 2000, Dallas, Texas, USA. IEEE Computer Society, CD-ROM, page 59. IEEE Computer Society, 2000. URL: https://doi.org/10.1109/SC.2000.10035.
  215. Kirk Schloegel, George Karypis, and Vipin Kumar. Parallel static and dynamic multi-constraint graph partitioning. Concurr. Comput. Pract. Exp., 14(3):219-240, 2002. URL: https://doi.org/10.1002/cpe.605.
  216. Dominik Schultes and Peter Sanders. Dynamic highway-node routing. In Camil Demetrescu, editor, Experimental Algorithms, 6th International Workshop, WEA 2007, Rome, Italy, June 6-8, 2007, Proc., volume 4525 of Lecture Notes in Computer Science, pages 66-79. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-72845-0_6.
  217. Dipanjan Sengupta, Narayanan Sundaram, Xia Zhu, Theodore L Willke, Jeffrey Young, Matthew Wolf, and Karsten Schwan. Graphin: An online high performance incremental graph processing framework. In European Conference on Parallel Processing, pages 319-333. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-43659-3_24.
  218. Neha Sengupta, Michael Hamann, and Dorothea Wagner. Benchmark generator for dynamic overlapping communities in networks. In Vijay Raghavan, Srinivas Aluru, George Karypis, Lucio Miele, and Xindong Wu, editors, 2017 IEEE International Conference on Data Mining, ICDM 2017, New Orleans, LA, USA, November 18-21, 2017, pages 415-424. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/ICDM.2017.51.
  219. Zhenzhen Shao, Na Guo, Yu Gu, Zhigang Wang, Fangfang Li, and Ge Yu. Efficient closeness centrality computation for dynamic graphs. In Yunmook Nah, Bin Cui, Sang-Won Lee, Jeffrey Xu Yu, Yang-Sae Moon, and Steven Euijong Whang, editors, Database Systems for Advanced Applications - 25th International Conference, DASFAA 2020, Jeju, South Korea, September 24-27, 2020, Proc., Part II, volume 12113 of Lecture Notes in Computer Science, pages 534-550. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-59416-9_32.
  220. Y. Shiloach and S. Even. An on-line edge-deletion problem. Journal of the ACM, 28(1):1-4, 1981. URL: https://doi.org/10.1145/322234.322235.
  221. Dhirendra Singh and Nilay Khare. Parallel batch dynamic single source shortest path algorithm and its implementation on GPU based machine. Int. Arab J. Inf. Technol., 16(2):217-225, 2019. URL: http://iajit.org/index.php?option=com_content&task=blogcategory&id=137&Itemid=469.
  222. Daniel Dominic Sleator and Robert Endre Tarjan. A data structure for dynamic trees. In Proc. of the 13th Annual ACM Symposium on Theory of Computing, May 11-13, 1981, Milwaukee, Wisconsin, USA, pages 114-122. ACM, 1981. URL: https://doi.org/10.1145/800076.802464.
  223. Shay Solomon. Fully dynamic maximal matching in constant update time. In 57th Symposium on Foundations of Computer Science FOCS, pages 325-334, 2016. URL: https://doi.org/10.1109/FOCS.2016.43.
  224. Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, and Eli Upfal. Trièst: Counting local and global triangles in fully dynamic streams with fixed memory size. ACM Trans. Knowl. Discov. Data, 11(4):43:1-43:50, 2017. URL: https://doi.org/10.1145/3059194.
  225. Daniel Stubbs and Virginia Vassilevska Williams. Metatheorems for dynamic weighted matching. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 58:1-58:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.58.
  226. Bintao Sun, T.-H. Hubert Chan, and Mauro Sozio. Fully dynamic approximate k-core decomposition in hypergraphs. ACM Trans. Knowl. Discov. Data, 14(4), May 2020. URL: https://doi.org/10.1145/3385416.
  227. Robert Endre Tarjan and Renato Fonseca F. Werneck. Dynamic trees in practice. ACM J. Exp. Algorithmics, 14, 2009. URL: https://doi.org/10.1145/1498698.1594231.
  228. Mikkel Thorup. Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In Torben Hagerup and Jyrki Katajainen, editors, Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, Proceedings, volume 3111 of Lecture Notes in Computer Science, pages 384-396. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-27810-8_33.
  229. Mikkel Thorup. Worst-case update times for fully-dynamic all-pairs shortest paths. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 112-119. ACM, 2005. URL: https://doi.org/10.1145/1060590.1060607.
  230. Mikkel Thorup. Fully-dynamic min-cut. Comb., 27(1):91-127, 2007. URL: https://doi.org/10.1007/s00493-007-0045-2.
  231. Mikkel Thorup and David R. Karger. Dynamic graph algorithms with applications. In Magnús M. Halldórsson, editor, Algorithm Theory - SWAT 2000, 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 5-7, 2000, Proceedings, volume 1851 of Lecture Notes in Computer Science, pages 1-9. Springer, 2000. URL: https://doi.org/10.1007/3-540-44985-X_1.
  232. Thomas Tseng, Laxman Dhulipala, and Guy E. Blelloch. Batch-parallel euler tour trees. In Stephen G. Kobourov and Henning Meyerhenke, editors, Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, USA, January 7-8, 2019, pages 92-106. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975499.8.
  233. Jan van den Brand and Danupon Nanongkai. Dynamic approximate shortest paths and beyond: Subquadratic and worst-case update time. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 436-455. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00035.
  234. Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 456-480. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00036.
  235. Alexander van der Grinten, Elisabetta Bergamini, Oded Green, David A. Bader, and Henning Meyerhenke. Scalable katz ranking computation in large static and dynamic graphs. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pages 42:1-42:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.42.
  236. Luis M. Vaquero, Félix Cuadrado, Dionysios Logothetis, and Claudio Martella. xdgp: A dynamic graph processing system with adaptive partitioning. CoRR, abs/1309.1049, 2013. URL: http://arxiv.org/abs/1309.1049.
  237. Luis M. Vaquero, Félix Cuadrado, Dionysios Logothetis, and Claudio Martella. Adaptive partitioning for large-scale dynamic graphs. In IEEE 34th International Conference on Distributed Computing Systems, ICDCS 2014, Madrid, Spain, June 30 - July 3, 2014, pages 144-153. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/ICDCS.2014.23.
  238. Tanmay Verma and Dhruv Batra. Maxflow revisited: An empirical comparison of maxflow algorithms for dense vision problems. In Richard Bowden, John P. Collomosse, and Krystian Mikolajczyk, editors, British Machine Vision Conference, BMVC 2012, Surrey, UK, September 3-7, 2012, pages 1-12. BMVA Press, 2012. URL: https://doi.org/10.5244/C.26.61.
  239. Dorothea Wagner, Thomas Willhalm, and Christos D. Zaroliagis. Geometric containers for efficient shortest-path computation. ACM J. Exp. Algorithmics, 10, 2005. URL: https://doi.org/10.1145/1064546.1103378.
  240. Chris Walshaw, Mark Cross, and Martin G. Everett. Parallel dynamic graph partitioning for adaptive unstructured meshes. J. Parallel Distributed Comput., 47(2):102-108, 1997. URL: https://doi.org/10.1006/jpdc.1997.1407.
  241. Jingjing Wang, Yanhao Wang, Wenjun Jiang, Yuchen Li, and Kian-Lee Tan. Efficient sampling algorithms for approximate temporal motif counting. In Mathieu d'Aquin, Stefan Dietze, Claudia Hauff, Edward Curry, and Philippe Cudré-Mauroux, editors, CIKM '20: The 29th ACM International Conference on Information and Knowledge Management, Virtual Event, Ireland, October 19-23, 2020, pages 1505-1514. ACM, 2020. URL: https://doi.org/10.1145/3340531.3411862.
  242. Na Wang, Dongxiao Yu, Hai Jin, Chen Qian, Xia Xie, and Qiang-Sheng Hua. Parallel algorithm for core maintenance in dynamic graphs. In Kisung Lee and Ling Liu, editors, 37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017, Atlanta, GA, USA, June 5-8, 2017, pages 2366-2371. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/ICDCS.2017.288.
  243. Stefan Weigert, Matti Hiltunen, and Christof Fetzer. Mining large distributed log data in near real time. In Managing Large-scale Systems via the Analysis of System Logs and the Application of Machine Learning Techniques, pages 1-8. Association for Computing Machinery, 2011. URL: https://doi.org/10.1145/2038633.2038638.
  244. Martin Winter, Daniel Mlakar, Rhaleb Zayer, Hans-Peter Seidel, and Markus Steinberger. faimgraph: high performance management of fully-dynamic graphs under tight memory constraints on the GPU. In Proc. of the International Conference for High Performance Computing, Networking, Storage, and Analysis, SC 2018, Dallas, TX, USA, November 11-16, 2018, pages 60:1-60:13. IEEE / ACM, 2018. URL: http://dl.acm.org/citation.cfm?id=3291736.
  245. Ning Xu, Lei Chen, and Bin Cui. Loggp: a log-based dynamic graph partitioning method. Proc. of the VLDB Endowment, 7(14):1917-1928, 2014. URL: https://doi.org/10.14778/2733085.2733097.
  246. Bohua Yang, Dong Wen, Lu Qin, Ying Zhang, Xubo Wang, and Xuemin Lin. Fully dynamic depth-first search in directed graphs. Proc. VLDB Endow., 13(2):142-154, 2019. URL: https://doi.org/10.14778/3364324.3364329.
  247. Chia-Chen Yen, Mi-Yen Yeh, and Ming-Syan Chen. An efficient approach to updating closeness centrality and average path length in dynamic networks. In Hui Xiong, George Karypis, Bhavani M. Thuraisingham, Diane J. Cook, and Xindong Wu, editors, 2013 IEEE 13th International Conference on Data Mining, Dallas, TX, USA, December 7-10, 2013, pages 867-876. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/ICDM.2013.135.
  248. Anita Zakrzewska and David A. Bader. Fast incremental community detection on dynamic graphs. In Roman Wyrzykowski, Ewa Deelman, Jack Dongarra, Konrad Karczewski, Jacek Kitowski, and Kazimierz Wiatr, editors, Parallel Processing and Applied Mathematics, pages 207-217, Cham, 2016. Springer International Publishing. URL: https://doi.org/10.1007/978-3-319-32149-3_20.
  249. Christos D Zaroliagis. Implementations and experimental studies of dynamic graph algorithms. In Experimental algorithmics, pages 229-278. Springer, 2002. URL: https://doi.org/10.1007/3-540-36383-1_11.
  250. Yikai Zhang, Jeffrey Xu Yu, Ying Zhang, and Lu Qin. A fast order-based approach for core maintenance. In 33rd IEEE International Conference on Data Engineering, ICDE 2017, San Diego, CA, USA, April 19-22, 2017, pages 337-348. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/ICDE.2017.93.
  251. Weiguo Zheng, Chengzhi Piao, Hong Cheng, and Jeffrey Xu Yu. Computing a near-maximum independent set in dynamic graphs. In 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8-11, 2019, pages 76-87. IEEE, 2019. URL: https://doi.org/10.1109/ICDE.2019.00016.
  252. Weiguo Zheng, Qichen Wang, Jeffrey Xu Yu, Hong Cheng, and Lei Zou. Efficient computation of a near-maximum independent set over evolving graphs. In 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, April 16-19, 2018, pages 869-880. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/ICDE.2018.00083.
  253. Lei Zhu, Shaoning Pang, Abdolhossein Sarrafzadeh, Tao Ban, and Daisuke Inoue. Incremental and decremental max-flow for online semi-supervised learning. IEEE Trans. Knowl. Data Eng., 28(8):2115-2127, 2016. URL: https://doi.org/10.1109/TKDE.2016.2550042.
  254. Di Zhuang, Morris J Chang, and Mingchen Li. Dynamo: Dynamic community detection by incrementally maximizing modularity. IEEE Transactions on Knowledge and Data Engineering, 2019. URL: https://doi.org/10.1109/TKDE.2019.2951419.
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