Open Access Open Access  Restricted Access Subscription or Fee Access

A Brief Survey on Distributed Graph Algorithms for Shortest Distance

V. Jenifer

Abstract


There is an extended history of study in theoretical computer science faithful to designing proficient algorithms for graph problems. In several modern applications the graph in query is altering over time, and to avoid rerunning algorithm on the entire graph every time a small change occurs. This paper aims to present a brief survey on graph theory based on Shortest Distances in Dynamic Graphs techniques in which the goal is to minimize the amount of work needed to re-optimize the solution when the graph changes. Number of relative studies namely Graph pattern matching, Spatially Induced Linkage Cognizance (SILC), Snowball Algorithm, GREEDY-SNDOP, APSP and Efficient incremental algorithms are discussed and evaluate the running time performance on the several datasets. Comparing to these algorithms the efficient incremental algorithm techniques methods outperforms having better performance than other methods.


Keywords


Datamining, Dynamic Graph, Shortest Distance, Incremental Algorithms.

Full Text:

PDF

References


Xingquan Zhu, Ian Davidson, “Knowledge Discovery and Data Mining: Challenges and Realities”, ISBN 978-1-59904-252, Hershey, New York, 2007.

W. Fan, J. Li, S. Ma, N. Tang, Y. Wu, and Y. Wu, “Graph pattern matching: From intractable to polynomial time,” Proc. VLDB Endowment, vol. 3, no. 1, pp. 264–275, 2010.

L. Wu, X. Xiao, D. Deng, G. Cong, A. D. Zhu, and S. Zhou, “Shortest path and distance queries on road networks: An experimental evaluation,” Proc. VLDB Endowment, vol. 5, no. 5, pp. 406–417, 2012.

L. Planken, M. de Weerdt, and R. van der Krogt, “Computing allpairs shortest paths by leveraging low treewidth,” J. Artif. Intell. Res., vol. 43, pp. 353–388, 2012.

P. Shakarian, M. Broecheler, V. S. Subrahmanian, and C. Molinaro, “Using generalized annotated programs to solve social network diffusion optimization problems,” ACM Trans. Comput. Logic, vol. 14, no. 2, pp. 10:1–10:40, 2013.

S. S. Khopkar, R. Nagi, A. G. Nikolaev, and V. Bhembre, “Efficient algorithms for incremental all pairs shortest paths, closeness and betweenness in social network analysis,” Social Netw. Analys. Mining, vol. 4, no. 1, 2014, Art. no. 220.

F. Bonchi, A. Gionis, F. Gullo, and A. Ukkonen, “Distance oracles in edge-labeled graphs,” in Proc. Int. Conf. Extending Database Technol., 2014, pp. 547–558.

A. Tagarelli and R. Interdonato, “Time-aware analysis and ranking of lurkers in social networks,” Social Netw. Analys. Mining, vol. 5, no. 1, pp. 46:1–46:23, 2015.

S. Greco, C. Molinaro, and C. Pulice, “Efficient maintenance of allpairs shortest distances,” in Proc. Sci. Statistical Database Manag., 2016, pp. 9:1–9:12.

Sergio Greco, Cristian Molinaro , and Chiara Pulice, "Efficient Maintenance of Shortest Distances in Dynamic Graphs", IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 30, NO. 3, MARCH 2018.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.