### Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates: New Algorithms and ExperimentsDynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates: New Algorithms and Experiments

Access Restriction
Subscribed

 Author Dandrea, Annalisa ♦ Demidio, Mattia ♦ Frigioni, Daniele ♦ Leucci, Stefano ♦ Proietti, Guido Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Shortest-path tree ♦ Batch algorithms ♦ Dynamic networks Abstract A dynamic graph algorithm is called $\textit{batch}$ if it is able to update efficiently the solution of a given graph problem after $\textit{multiple}$ updates at a time (i.e., a batch) take place on the input graph. In this article, we study batch algorithms for maintaining a single-source shortest-path tree in graphs with positive real edge weights. In particular, we focus our attention on $\textit{homogeneous}$ batches, that is, either $\textit{incremental}$ (containing only edge insertion and weight decrease operations) or $\textit{decremental}$ (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. 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 update sensitive; 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. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-07-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 20 Page Count 33 Starting Page 1 Ending Page 33

#### Open content in new tab

Source: ACM Digital Library