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

摘要

A dynamic graph algorithm is called batch if it is able to update efficiently the solution of a given graphrnproblem after multiple updates at a time (i.e., a batch) take place on the input graph. In this article, we studyrnbatch algorithms for maintaining a single-source shortest-path tree in graphs with positive real edge weights.rnIn particular,we focus our attention on homogeneous batches, that is, either incremental (containing only edgerninsertion and weight decrease operations) or decremental (containing only edge deletion and weight increasernoperations) batches, which model realistic dynamic scenarios like transient vertex failures in communicationrnnetworks and traffic congestion/decongestion phenomena in road networks.rnWe propose two new algorithms to process either incremental or decremental batches, respectively, and arncombination of these two algorithms that is able to process arbitrary sequences of incremental and decrementalrnbatches. All these algorithms are update sensitive; namely, they are efficient with respect to thernnumber of vertices in the shortest-path tree that change their parents and/or their distances from the sourcernas a consequence of a batch. This makes unfeasible an effective comparison on a theoretical basis of our newrnalgorithms with the solutions known in the literature, which in turn are analyzed with respect to othersrnand different parameters. For this reason, in order to evaluate the quality of our approach, we providernalso an extensive experimental study including our new algorithms and the most efficient previous batchrnalgorithms. Our experimental results complement previous studies and show that the various solutions canrnbe consistently ranked on the basis of the type of homogeneous batch and of the underlying network. As arnresult, our work can be helpful in selecting a proper solution depending on the specific application scenario.