Please use this identifier to cite or link to this item:
Title: An adaptive amoeba algorithm for shortest path tree computation in dynamic graphs
Authors: Zhang, XG
Chan, FTS 
Yang, H
Deng, Y
Keywords: Shortest path tree
Dynamic graphs
Graph algorithms
Routing protocols
Issue Date: 2017
Publisher: Elsevier
Source: Information sciences, 2017, v. 405, p. 123-140 How to cite?
Journal: Information sciences 
Abstract: In today's Internet, the shortest path tree (SPT) construction is an important issue in data exchange. To forward a data packet, each router uses routing protocols and link state information to identify the shortest paths from itself to other routers, which yields the shortest path tree. In reality, the network topology often varies over time. In existing studies, the locally affected nodes are identified and the shortest paths are recomputed so as to update the SPT. However, when the network size becomes large, the process of reconstructing the shortest paths for the affected nodes is very time consuming. Herein, we propose an adaptive amoeba method to build SPT in dynamic graphs. The proposed method is illustrated using a three-step procedure. First, we generalize the original Physarum model to enable it to have the ability to find the shortest paths in directed graphs. Secondly, the Physarum model is further extended to construct the shortest path tree when there are multiple sink nodes. Finally, we demonstrate that the developed method is capable of reconstructing the SPT by adapting the tube flow when link weight changes occur. Different from previous methods, the proposed algorithm is capable of identifying and recomputing the shortest paths for the affected nodes as well as maintaining the original paths for the unaffected vertices spontaneously. We demonstrate the performance of the proposed algorithm by comparing it with the Label Setting algorithm and Dijkstra algorithm in four randomly generated graphs. The computational results suggest the most appropriate algorithms to be used in different scenarios.
ISSN: 0020-0255
EISSN: 1872-6291
DOI: 10.1016/j.ins.2017.04.021
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Dec 13, 2018


Last Week
Last month
Citations as of Dec 13, 2018

Page view(s)

Last Week
Last month
Citations as of Dec 9, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.