Access Restriction

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

   Open content in new tab
Source: ACM Digital Library