{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:14:13Z","timestamp":1750306453488,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2015,7,15]],"date-time":"2015-07-15T00:00:00Z","timestamp":1436918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Italian Ministry of University and Research","award":["2010N5K7EB PRIN 2010 and 2012C4E3KT PRIN 2012"],"award-info":[{"award-number":["2010N5K7EB PRIN 2010 and 2012C4E3KT PRIN 2012"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2015,12,15]]},"abstract":"<jats:p>\n            A dynamic graph algorithm is called\n            <jats:italic>batch<\/jats:italic>\n            if it is able to update efficiently the solution of a given graph problem after\n            <jats:italic>multiple<\/jats:italic>\n            updates at a time (i.e., a batch) take place on the input graph. In this article, we study batch algorithms for maintaining a\n            <jats:italic>single-source shortest-path tree<\/jats:italic>\n            in graphs with positive real edge weights. In particular, we focus our attention on\n            <jats:italic>homogeneous<\/jats:italic>\n            batches, that is, either\n            <jats:italic>incremental<\/jats:italic>\n            (containing only edge insertion and weight decrease operations) or\n            <jats:italic>decremental<\/jats:italic>\n            (containing only edge deletion and weight increase operations) batches, which model realistic dynamic scenarios like transient vertex failures in communication networks and traffic congestion\/decongestion phenomena in road networks.\n          <\/jats:p>\n          <jats:p>\n            We propose two new algorithms to process either incremental or decremental batches, respectively, and a combination of these two algorithms that is able to process arbitrary sequences of incremental and decremental batches. All these algorithms are\n            <jats:italic>update sensitive<\/jats:italic>\n            ; namely, they are efficient with respect to the number of vertices in the shortest-path tree that change their parents and\/or their distances from the source as a consequence of a batch. This makes unfeasible an effective comparison on a theoretical basis of our new algorithms with the solutions known in the literature, which in turn are analyzed with respect to others and different parameters. For this reason, in order to evaluate the quality of our approach, we provide also an extensive experimental study including our new algorithms and the most efficient previous batch algorithms. Our experimental results complement previous studies and show that the various solutions can be consistently ranked on the basis of the type of homogeneous batch and of the underlying network. As a result, our work can be helpful in selecting a proper solution depending on the specific application scenario.\n          <\/jats:p>","DOI":"10.1145\/2786022","type":"journal-article","created":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T13:21:25Z","timestamp":1437139285000},"page":"1-33","source":"Crossref","is-referenced-by-count":4,"title":["Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates"],"prefix":"10.1145","volume":"20","author":[{"given":"Annalisa","family":"D'Andrea","sequence":"first","affiliation":[{"name":"University of L'Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mattia","family":"D'Emidio","sequence":"additional","affiliation":[{"name":"University of L'Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniele","family":"Frigioni","sequence":"additional","affiliation":[{"name":"University of L'Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[{"name":"University of L'Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[{"name":"University of L'Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10)","author":"Abraham I.","key":"e_1_2_1_2_1","unstructured":"I. Abraham , A. Fiat , A. V. Goldberg , and R. F. Werneck . 2010. Highway dimension, shortest paths, and provably efficient algorithms . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10) . Society for Industrial and Applied Mathematics, 782--793. I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck. 2010. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10). Society for Industrial and Applied Mathematics, 782--793."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_4_1","volume-title":"Technical Report MSR-TR-2014-4. Microsoft Research.","author":"Bast H.","year":"2014","unstructured":"H. Bast , D. Delling , A. Goldberg , M. Mueller-Hannemann , T. Pajor , P. Sanders , D. Wagner , and R. F. Werneck . 2014 . Route Planning in Transportation Networks . Technical Report MSR-TR-2014-4. Microsoft Research. H. Bast, D. Delling, A. Goldberg, M. Mueller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. F. Werneck. 2014. Route Planning in Transportation Networks. Technical Report MSR-TR-2014-4. Microsoft Research."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1671976"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488701"},{"volume-title":"Random Graphs","author":"Bollob\u00e1s B.","key":"e_1_2_1_8_1","unstructured":"B. Bollob\u00e1s . 2001. Random Graphs . Cambridge University Press . B. Bollob\u00e1s. 2001. Random Graphs. Cambridge University Press."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'96)","author":"Brodal G. S.","year":"1996","unstructured":"G. S. Brodal . 1996 . Worst-case efficient priority queues . In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'96) . ACM, 52--58. G. S. Brodal. 1996. Worst-case efficient priority queues. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'96). ACM, 52--58."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11786-007-0023-5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1070.0231"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2008.198"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2694605.2694637"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_24"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21542"},{"key":"e_1_2_1_16_1","volume-title":"10th International Symposium on Experimental Algorithms (SEA'11)","volume":"6630","author":"Delling D.","unstructured":"D. Delling , A. V. Goldberg , T. Pajor , and R. F. Werneck . 2011. Customizable route planning . In 10th International Symposium on Experimental Algorithms (SEA'11) (Lecture Notes in Computer Science) , Vol. 6630 . Springer, 376--387. D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. 2011. Customizable route planning. In 10th International Symposium on Experimental Algorithms (SEA'11) (Lecture Notes in Computer Science), Vol. 6630. Springer, 376--387."},{"key":"e_1_2_1_17_1","volume-title":"22th Annual European Symposium (ESA'14)","volume":"8737","author":"Delling D.","unstructured":"D. Delling , A. V. Goldberg , T. Pajor , and R. F. Werneck . 2014. Robust distance queries on massive networks . In 22th Annual European Symposium (ESA'14) (Lecture Notes in Computer Science) , Vol. 8737 . Springer, 321--333. D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. 2014. Robust distance queries on massive networks. In 22th Annual European Symposium (ESA'14) (Lecture Notes in Computer Science), Vol. 8737. Springer, 321--333."},{"key":"e_1_2_1_18_1","volume-title":"6th International Workshop on Experimental Algorithms (WEA'07)","volume":"4525","author":"Delling D.","unstructured":"D. Delling and D. Wagner . 2007. Landmark-based routing in dynamic graphs . In 6th International Workshop on Experimental Algorithms (WEA'07) (Lecture Notes in Computer Science) , Vol. 4525 . Springer, 52--65. D. Delling and D. Wagner. 2007. Landmark-based routing in dynamic graphs. In 6th International Workshop on Experimental Algorithms (WEA'07) (Lecture Notes in Computer Science), Vol. 4525. Springer, 52--65."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297147"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009224"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1048"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00082-8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05)","author":"Goldberg A. V.","key":"e_1_2_1_25_1","unstructured":"A. V. Goldberg and C. Harrelson . 2005. Computing the shortest path: A search meets graph theory . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05) . Society for Industrial and Applied Mathematics, 156--165. A. V. Goldberg and C. Harrelson. 2005. Computing the shortest path: A search meets graph theory. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05). Society for Industrial and Applied Mathematics, 156--165."},{"key":"e_1_2_1_26_1","unstructured":"Y. Hyun B. Huffaker D. Andersen E. Aben C. Shannon M. Luckie and KC Claffy. 2014. The CAIDA IPv4 Routed\/24 Topology Dataset. Retrieved from http:\/\/www.caida.org\/data\/active\/ipv4_routed_24_topology_dataset.xml.  Y. Hyun B. Huffaker D. Andersen E. Aben C. Shannon M. Luckie and KC Claffy. 2014. The CAIDA IPv4 Routed\/24 Topology Dataset. Retrieved from http:\/\/www.caida.org\/data\/active\/ipv4_routed_24_topology_dataset.xml."},{"key":"e_1_2_1_27_1","first-page":"219","article-title":"An extremely fast, exact algorithm for finding shortest paths","volume":"22","author":"Lauther U.","year":"2004","unstructured":"U. Lauther . 2004 . An extremely fast, exact algorithm for finding shortest paths . Static Networks with Geographical Background 22 , 219 -- 230 . U. Lauther. 2004. An extremely fast, exact algorithm for finding shortest paths. Static Networks with Geographical Background 22, 219--230.","journal-title":"Static Networks with Geographical Background"},{"key":"e_1_2_1_28_1","volume-title":"8th International Conference on Algorithms and Complexity (CIAC'13)","volume":"7878","author":"Mali G.","unstructured":"G. Mali , P. Michail , A. Paraskevopoulos , and C. Zaroliagis . 2013. A new dynamic graph structure for large-scale transportation networks . In 8th International Conference on Algorithms and Complexity (CIAC'13) (Lecture Notes in Computer Science) , Vol. 7878 . Springer, 312--323. G. Mali, P. Michail, A. Paraskevopoulos, and C. Zaroliagis. 2013. A new dynamic graph structure for large-scale transportation networks. In 8th International Conference on Algorithms and Complexity (CIAC'13) (Lecture Notes in Computer Science), Vol. 7878. Springer, 312--323."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.893870"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0046"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/090776573"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786022","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2786022","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:15Z","timestamp":1750225395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786022"}},"subtitle":["New Algorithms and Experiments"],"short-title":[],"issued":{"date-parts":[[2015,7,15]]},"references-count":32,"alternative-id":["10.1145\/2786022"],"URL":"https:\/\/doi.org\/10.1145\/2786022","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2015,7,15]]}}}