Dynamic networks are prevalent everywhere right from Internet, Local Area Networks, Mobile Ad hoc networks to Wireless Sensor Networks. Communication networks, social networks, Web, transportation networks infrastructures represent dynamic networks due to the dynamics that influence its topologies, connectivity, reliability and fault-tolerance. The network dynamics is rigorously influenced by the input parameters like data, communication, computational overloads, data traffic, data congestion, inclusion and exclusion of data resources over time. Hence, to identify optimal paths in such dynamic networks where communication nodes come and go, network communication edges may crash and recover, is a non-trivial problem. In this paper we present a rigorous study on various shortest path finding algorithms in dynamic networks. Although the research on this problem spans over more than thirty years, in the last couple of years many novel algorithmic techniques have been proposed. An arduous effort is made to abstract some combinatorial and algebraic properties. Also, common data-structural tools that are at the base of those techniques are described and compared.

 

Published In : IJCSN Journal Volume 2, Issue 6

Date of Publication : 01 December 2013

Pages : 184 - 195

Figures : 07

Tables : 04

Publication Link : ijcsn.org/IJCSN-2013/2-6/IJCSN-2013-2-6-161.pdf

 

 

 

Neeraj Navlakha : Department of Applied Mathematics, Defence Institute of Advanced Technology Pune, Maharashtra, 411025, India.

Manisha J. Nene : Department of Computer Engineering, Defence Institute of Advanced Technology Pune, Maharashtra, 411025, India.

 

 

 

 

 

 

 

Dynamic networks

dynamic graph problems

dynamic shortest paths

complexity

 

 

 

Identifying optimal paths in dynamic networks is a non-trivial problem. The applications, computations, processes, data etc. migrate from blade servers to handheld computational devices and vice-versa which belongs to a dynamic network demand for runtime optimal path detections. Throughout the paper we attempted to present all the algorithmic techniques within a unified framework by abstracting the algebraic and combinatorial properties and the data-structural tools that lie at their foundations. Simulation results on real-world graph of Maryland State in US show that the running time and memory dissipation are acceptable on relatively small network, and also on enquiry of safe path between a pair of nodes with relatively short distance. The time complexity is only about O(n^2.4 ) when algorithm 3 is applied in scale-free networks generated by the AB model. The algorithm performance is slightly improved with the optimization strategies in scale-free networks. Recent work has raised some new and perhaps intriguing questions. First, can we reduce the space usage for dynamic shortest paths to O(n^2 )? Second, and perhaps more important, can we solve efficiently fully dynamic single-source reachability and shortest paths on general graphs? Lastly, are there any general techniques for making increase-only algorithms fully dynamic, remains unanswered.

 

 

 

 

 

 

 

 

 

[1] Camil Demetrescu and Giuseppe F. Italiano. Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks. Electronic Notes in Theoretical Computer Science 171 (2007) 3–15.

[2] Wu Jigang, Song Jin, Haikun Ji, Thambipillai Srikanthan. Algorithm for Time-dependent Shortest Safe Path on Transportation Networks. International Conference on Computational Science, ICCS 2011, Procedia Computer Science 4 (2011) 958–966.

[3] Wei Peng, Xiaofeng Hu, Feng Zhao, Jinshu Su. A Fast Algorithm to Find All-Pairs Shortest Paths in Complex Networks. International Conference on Computational Science, ICCS 2012, Procedia Computer Science 9 (2012) 557 – 566.

[4] D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.

[5] P. Loubal. A network evaluation procedure. Highway Research Record 205, pages 96–109, 1967.

[6] J. Murchland. The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph. Technical report, LBS-TNT-26, London Business School, Transport Network Theory Unit, London, UK, 1967.

[7] V. Rodionov. The parametric problem of shortest distances. U.S.S.R. Computational Math. and Math. Phys., 8(5):336–343, 1968.

[8] S. Even and H. Gazit. Updating distances in dynamic graphs. Methods of Operations Research, 49:371–387, 1985.

[9] H. Rohnert. A dynamization of the all-pairs least cost problem. In Proc. 2nd Annual Symposium on Theoretical Aspects of Computer Science, (STACS’85), LNCS 182, pages 279–286, 1985.

[10] E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, vol.1, pp.269-271, 1959.

[11] R. Bellman. On a Routing Problem. Quarterly of Applied Mathematics, vol.16, no.1, pp.87-90, 1958.

[12] J. B. Orlin, K. Madduri, K. Subramani, and M. Williamson. A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths. Journal of Discrete Algorithms, vol.8, no.2, pp.189-198, June 2010.

[13] A. V. Goldberg, H. Kaplan, and R. F. Werneck. Reach for A*: Efficient Point-to-Point Shortest Path Algorithms. In Proc. of the Eighth Workshop on Algorithm Engineering and Experiments (ALENEX’06), Miami, Florida, USA, pp.129-143, Jan. 2006.

[14] L. Roditty and U. Zwick. On Dynamic Shortest Paths Problems. Algorithmica, March 2010 (published online).

[15] S. Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science, vol.312, no.1, pp.47-4, Jan. 2004.

[16] T. M. Chan. All-pairs shortest paths with real weights in O(n^3/log?n ) time. in: Proc. 9th Workshop Algorithms Data Structures, in: Lecture Notes in Computer Science, vol.3608, Springer, Berlin, 2005, pp.318-324.

[17] D. Bolin and Y. J. Xu and Q. Lu, Finding time-dependent shortest paths over large graphs, in Proceedings of the 11th international conference on Extending database technology, France, March 2008, pp. 205-216.

[18] P. Erd¨os and A. R´enyi. On the Evolution of Random Graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, vol.5, pp.17-61, 1960.

[19] R. Albert and A.-L. Barab´asi. Topology of Evolving Networks: Local Events and Universality. Physical Review Letters, vol.85, no.24, Dec. 2000.