[{"title":"Recent advances in fully dynamic graph algorithms","alternative_title":["LIPIcs"],"intvolume":"       221","publication_status":"published","article_processing_charge":"No","date_created":"2022-08-11T14:35:52Z","author":[{"full_name":"Hanauer, Kathrin","first_name":"Kathrin","last_name":"Hanauer"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Schulz, Christian","first_name":"Christian","last_name":"Schulz"}],"_id":"11808","scopus_import":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","abstract":[{"lang":"eng","text":"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."}],"arxiv":1,"doi":"10.4230/LIPIcs.SAND.2022.1","day":"29","external_id":{"arxiv":["2102.11169"]},"date_updated":"2023-02-14T08:14:41Z","citation":{"chicago":"Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Recent Advances in Fully Dynamic Graph Algorithms.” In <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">https://doi.org/10.4230/LIPIcs.SAND.2022.1</a>.","ieee":"K. Hanauer, M. H. Henzinger, and C. Schulz, “Recent advances in fully dynamic graph algorithms,” in <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, Virtual, 2022, vol. 221.","ama":"Hanauer K, Henzinger MH, Schulz C. Recent advances in fully dynamic graph algorithms. In: <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>. Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">10.4230/LIPIcs.SAND.2022.1</a>","apa":"Hanauer, K., Henzinger, M. H., &#38; Schulz, C. (2022). Recent advances in fully dynamic graph algorithms. In <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i> (Vol. 221). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">https://doi.org/10.4230/LIPIcs.SAND.2022.1</a>","ista":"Hanauer K, Henzinger MH, Schulz C. 2022. Recent advances in fully dynamic graph algorithms. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 1.","short":"K. Hanauer, M.H. Henzinger, C. Schulz, in:, 1st Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","mla":"Hanauer, Kathrin, et al. “Recent Advances in Fully Dynamic Graph Algorithms.” <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, vol. 221, 1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">10.4230/LIPIcs.SAND.2022.1</a>."},"year":"2022","extern":"1","volume":221,"month":"04","article_number":"1","oa_version":"Published Version","publication":"1st Symposium on Algorithmic Foundations of Dynamic Networks","conference":{"start_date":"2022-03-28","name":"SAND: Symposium on Algorithmic Foundations of Dynamic Networks","location":"Virtual","end_date":"2022-03-30"},"language":[{"iso":"eng"}],"oa":1,"publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959772242"]},"date_published":"2022-04-29T00:00:00Z","type":"conference","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.SAND.2022.1","open_access":"1"}]},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.SAND.2022.18"}],"oa":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772242"]},"type":"conference","date_published":"2022-04-29T00:00:00Z","conference":{"name":"SAND: Symposium on Algorithmic Foundations of Dynamic Networks","start_date":"2022-04-28","location":"Virtual","end_date":"2022-04-30"},"language":[{"iso":"eng"}],"article_number":"18","month":"04","oa_version":"Published Version","publication":"1st Symposium on Algorithmic Foundations of Dynamic Networks","extern":"1","volume":221,"abstract":[{"text":"This paper presents a comprehensive study of algorithms for maintaining the number of all connected four-vertex subgraphs in a dynamic graph. Specifically, our algorithms maintain the number of paths of length three in deterministic amortized O(m^{1/2}) update time, and any other connected four-vertex subgraph which is not a clique in deterministic amortized update time O(m^{2/3}). Queries can be answered in constant time. We also study the query times for subgraphs containing an arbitrary edge that is supplied only with the query as well as the case where only subgraphs containing a vertex s that is fixed beforehand are considered. For length-3 paths, paws, 4-cycles, and diamonds our bounds match or are not far from (conditional) lower bounds: Based on the OMv conjecture we show that any dynamic algorithm that detects the existence of paws, diamonds, or 4-cycles or that counts length-3 paths takes update time Ω(m^{1/2-δ}).\r\nAdditionally, for 4-cliques and all connected induced subgraphs, we show a lower bound of Ω(m^{1-δ}) for any small constant δ > 0 for the amortized update time, assuming the static combinatorial 4-clique conjecture holds. This shows that the O(m) algorithm by Eppstein et al. [David Eppstein et al., 2012] for these subgraphs cannot be improved by a polynomial factor.","lang":"eng"}],"day":"29","arxiv":1,"doi":"10.4230/LIPIcs.SAND.2022.18","external_id":{"arxiv":["2106.15524"]},"year":"2022","citation":{"mla":"Hanauer, Kathrin, et al. “Fully Dynamic Four-Vertex Subgraph Counting.” <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, vol. 221, 18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.18\">10.4230/LIPIcs.SAND.2022.18</a>.","short":"K. Hanauer, M.H. Henzinger, Q.C. Hua, in:, 1st Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ista":"Hanauer K, Henzinger MH, Hua QC. 2022. Fully dynamic four-vertex subgraph counting. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 18.","ama":"Hanauer K, Henzinger MH, Hua QC. Fully dynamic four-vertex subgraph counting. In: <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>. Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.18\">10.4230/LIPIcs.SAND.2022.18</a>","apa":"Hanauer, K., Henzinger, M. H., &#38; Hua, Q. C. (2022). Fully dynamic four-vertex subgraph counting. In <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i> (Vol. 221). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.18\">https://doi.org/10.4230/LIPIcs.SAND.2022.18</a>","ieee":"K. Hanauer, M. H. Henzinger, and Q. C. Hua, “Fully dynamic four-vertex subgraph counting,” in <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, Virtual, 2022, vol. 221.","chicago":"Hanauer, Kathrin, Monika H Henzinger, and Qi Cheng Hua. “Fully Dynamic Four-Vertex Subgraph Counting.” In <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.18\">https://doi.org/10.4230/LIPIcs.SAND.2022.18</a>."},"date_updated":"2023-02-14T08:25:42Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","intvolume":"       221","alternative_title":["LIPIcs"],"title":"Fully dynamic four-vertex subgraph counting","article_processing_charge":"No","date_created":"2022-08-12T06:57:55Z","publication_status":"published","author":[{"full_name":"Hanauer, Kathrin","first_name":"Kathrin","last_name":"Hanauer"},{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Qi Cheng","last_name":"Hua","full_name":"Hua, Qi Cheng"}],"scopus_import":"1","_id":"11812"}]