An Adaptive Amoeba Algorithm for Shortest Path Tree Computation in Dynamic Graphs
This addresses the complexity of updating shortest path trees in large dynamic networks, though it appears incremental as it builds on existing methods for handling edge weight changes.
The paper tackles the shortest path tree problem in dynamic graphs by proposing an adaptive amoeba algorithm that automatically identifies and reconstructs affected vertices when edge weights change, showing effectiveness in comparisons with Label Setting and Bellman-Ford algorithms.
This paper presents an adaptive amoeba algorithm to address the shortest path tree (SPT) problem in dynamic graphs. In dynamic graphs, the edge weight updates consists of three categories: edge weight increases, edge weight decreases, the mixture of them. Existing work on this problem solve this issue through analyzing the nodes influenced by the edge weight updates and recompute these affected vertices. However, when the network becomes big, the process will become complex. The proposed method can overcome the disadvantages of the existing approaches. The most important feature of this algorithm is its adaptivity. When the edge weight changes, the proposed algorithm can recognize the affected vertices and reconstruct them spontaneously. To evaluate the proposed adaptive amoeba algorithm, we compare it with the Label Setting algorithm and Bellman-Ford algorithm. The comparison results demonstrate the effectiveness of the proposed method.