{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T16:36:24Z","timestamp":1756571784773,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T00:00:00Z","timestamp":1548806400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Italian National Group for Scientific Computation GNCS-INdAM"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            The 2-hop Cover labeling of a graph is currently the best data structure for answering shortest-path distance queries on large-scale networks, since it combines low query times, affordable space occupancy, and reasonable preprocessing effort. Its main limit resides in not being suited for\n            <jats:italic>dynamic<\/jats:italic>\n            networks since, after a network change, (1) queries on the distance can return incorrect values and (2) recomputing the labeling\n            <jats:italic>from scratch<\/jats:italic>\n            yields unsustainable time overhead.\n          <\/jats:p>\n          <jats:p>\n            In this article, we overcome this limit by introducing the first\n            <jats:italic>decremental<\/jats:italic>\n            algorithm able to update 2-hop Cover labelings under node\/edge\n            <jats:italic>removals<\/jats:italic>\n            and edge\n            <jats:italic>weight increases<\/jats:italic>\n            . We prove the new algorithm to be (1) correct, i.e., after each update operation queries on the updated labeling return exact values; (2) efficient with respect to the number of nodes that change their distance as a consequence of a graph update; and (3) able to preserve the\n            <jats:italic>minimality<\/jats:italic>\n            of the labeling, a desirable property that impacts on both query time and space occupancy.\n          <\/jats:p>\n          <jats:p>\n            Furthermore, we provide an extensive experimental study to demonstrate the effectiveness of the new method. We consider it both alone and in combination with the unique known\n            <jats:italic>incremental<\/jats:italic>\n            approach\u00a0(Akiba et al. 2014), thus obtaining the first\n            <jats:italic>fully dynamic<\/jats:italic>\n            algorithm for updating 2-hop Cover labelings under general graph updates. Our experiments show that the new dynamic algorithms are orders of magnitude faster than the from-scratch approach while at the same time being able to preserve the quality of the labeling in terms of query time and space occupancy, thus allowing one to employ the 2-hop Cover labeling approach in dynamic networks with practical performance.\n          <\/jats:p>","DOI":"10.1145\/3299901","type":"journal-article","created":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T12:58:34Z","timestamp":1548853114000},"page":"1-36","source":"Crossref","is-referenced-by-count":22,"title":["Fully Dynamic 2-Hop Cover Labeling"],"prefix":"10.1145","volume":"24","author":[{"given":"Gianlorenzo","family":"D'angelo","sequence":"first","affiliation":[{"name":"Gran Sasso Science Institute (GSSI), L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7833-9520","authenticated-orcid":false,"given":"Mattia","family":"D'emidio","sequence":"additional","affiliation":[{"name":"University of L\u2019Aquila, L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2180-8813","authenticated-orcid":false,"given":"Daniele","family":"Frigioni","sequence":"additional","affiliation":[{"name":"University of L\u2019Aquila, L\u2019Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,1,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566486.2568007"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.74.47"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02011-7_7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2005.10.009"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11786-007-0023-5"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/6979.994796"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516417"},{"key":"e_1_2_1_10_1","volume-title":"14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS\u201914)","volume":"42","author":"Cionini A.","unstructured":"A. Cionini , G. D\u2019Angelo , M. D\u2019Emidio , D. Frigioni , K. Giannakopoulou , A. Paraskevopoulos , and C. D. Zaroliagis . 2014. Engineering graph-based models for dynamic timetable information systems . In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS\u201914) (OASICS), Vol. 42 . Schloss Dagstuhl, 46--61. A. Cionini, G. D\u2019Angelo, M. D\u2019Emidio, D. Frigioni, K. Giannakopoulou, A. Paraskevopoulos, and C. D. Zaroliagis. 2014. Engineering graph-based models for dynamic timetable information systems. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS\u201914) (OASICS), Vol. 42. Schloss Dagstuhl, 46--61."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"A. Cionini G. D\u2019Angelo M. D\u2019Emidio D. Frigioni K. Giannakopoulou A. Paraskevopoulos and C. D. Zaroliagis. 2017. Engineering graph-based models for dynamic timetable information systems. Journal of Discrete Algorithms 46--47 (2017) 40--58.  A. Cionini G. D\u2019Angelo M. D\u2019Emidio D. Frigioni K. Giannakopoulou A. Paraskevopoulos and C. D. Zaroliagis. 2017. Engineering graph-based models for dynamic timetable information systems. Journal of Discrete Algorithms 46--47 (2017) 40--58.","DOI":"10.1016\/j.jda.2017.09.001"},{"volume-title":"13th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902)","author":"Cohen E.","key":"e_1_2_1_12_1","unstructured":"E. Cohen , E. Halperin , H. Kaplan , and U. Zwick . 2002. Reachability and distance queries via 2-hop labels . In 13th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902) . ACM\/SIAM, 937--946. E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. 2002. Reachability and distance queries via 2-hop labels. In 13th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902). ACM\/SIAM, 937--946."},{"key":"e_1_2_1_13_1","volume-title":"20th International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201913)","volume":"8179","author":"D\u2019Andrea A.","unstructured":"A. D\u2019Andrea , M. D\u2019Emidio , D. Frigioni , S. Leucci , and G. Proietti . 2013. Dynamically maintaining shortest path trees under batches of updates. In 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201913) (Lecture Notes in Computer Science) , Vol. 8179 . Springer, 286--297. A. D\u2019Andrea, M. D\u2019Emidio, D. Frigioni, S. Leucci, and G. Proietti. 2013. Dynamically maintaining shortest path trees under batches of updates. In 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201913) (Lecture Notes in Computer Science), Vol. 8179. Springer, 286--297."},{"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.1145\/2786022"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21542"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.11.001"},{"key":"e_1_2_1_18_1","volume-title":"27th International Workshop on Combinatorial Algorithms (IWOCA\u201916)","volume":"9843","author":"D\u2019Angelo G.","unstructured":"G. D\u2019Angelo , M. D\u2019Emidio , and D. Frigioni . 2016. Distance queries in large-scale fully dynamic complex networks . In 27th International Workshop on Combinatorial Algorithms (IWOCA\u201916) (Lecture Notes in Computer Science) , Vol. 9843 . Springer, 109--121. G. D\u2019Angelo, M. D\u2019Emidio, and D. Frigioni. 2016. Distance queries in large-scale fully dynamic complex networks. In 27th International Workshop on Combinatorial Algorithms (IWOCA\u201916) (Lecture Notes in Computer Science), Vol. 9843. Springer, 109--121."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings, Part II (Lecture Notes in Computer Science)","volume":"6783","author":"D\u2019Angelo G.","unstructured":"G. D\u2019Angelo , M. D\u2019Emidio , D. Frigioni , and V. Maurizio . 2011. A speed-up technique for distributed shortest paths computation. In Computational Science and Its Applications (ICCSA\u201911) - International Conference. Proceedings, Part II (Lecture Notes in Computer Science) , Vol. 6783 . Springer, 578--593. G. D\u2019Angelo, M. D\u2019Emidio, D. Frigioni, and V. Maurizio. 2011. A speed-up technique for distributed shortest paths computation. In Computational Science and Its Applications (ICCSA\u201911) - International Conference. Proceedings, Part II (Lecture Notes in Computer Science), Vol. 6783. Springer, 578--593."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_13"},{"key":"e_1_2_1_21_1","volume-title":"10th International Symposium on Experimental Algorithms (SEA\u201911)","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\u201911) (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\u201911) (Lecture Notes in Computer Science), Vol. 6630. Springer, 376--387."},{"key":"e_1_2_1_22_1","volume-title":"22th European Symposium on Algorithms (ESA\u201914)","volume":"8737","author":"Delling D.","unstructured":"D. Delling , A. V. Goldberg , T. Pajor , and R. F. Werneck . 2014a. Robust distance queries on massive networks . In 22th European Symposium on Algorithms (ESA\u201914) (Lecture Notes in Computer Science) , Vol. 8737 . Springer, 321--333. D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. 2014a. Robust distance queries on massive networks. In 22th European Symposium on Algorithms (ESA\u201914) (Lecture Notes in Computer Science), Vol. 8737. Springer, 321--333."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_22"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674918.2674923"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536346"},{"volume-title":"10th Workshop on Algorithm Engineering and Experiments (ALENEX\u201908)","author":"Geisberger R.","key":"e_1_2_1_26_1","unstructured":"R. Geisberger , P. Sanders , and D. Schultes . 2008. Better approximation of betweenness centrality . In 10th Workshop on Algorithm Engineering and Experiments (ALENEX\u201908) . Society for Industrial and Applied Mathematics, 90--100. R. Geisberger, P. Sanders, and D. Schultes. 2008. Better approximation of betweenness centrality. In 10th Workshop on Algorithm Engineering and Experiments (ALENEX\u201908). Society for Industrial and Applied Mathematics, 90--100."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_43"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983731"},{"key":"e_1_2_1_29_1","unstructured":"Y. Hyun B. Huffaker D. Andersen E. Aben C. Shannon M. Luckie and K. C. 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 K. C. 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_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213887"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646063"},{"volume-title":"18th International Conference on Extending Database Technology (EDBT\u201915)","author":"Qin Y.","key":"e_1_2_1_32_1","unstructured":"Y. Qin , Q. Z. Sheng , and W. E. Zhang . 2015. SIEF: Efficiently answering distance queries for failure prone graphs . In 18th International Conference on Extending Database Technology (EDBT\u201915) . OpenProceedings.org, 145--156. Y. Qin, Q. Z. Sheng, and W. E. Zhang. 2015. SIEF: Efficiently answering distance queries for failure prone graphs. In 18th International Conference on Extending Database Technology (EDBT\u201915). OpenProceedings.org, 145--156."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321520"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3299901","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3299901","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:38Z","timestamp":1750204418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3299901"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,30]]},"references-count":34,"alternative-id":["10.1145\/3299901"],"URL":"https:\/\/doi.org\/10.1145\/3299901","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2019,1,30]]}}}