Software Engineering

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

A Brief Survey on Distributed Graph Algorithms For Shortest Distance


Affiliations
1 KG College of Arts and Science, Coimbatore., India
     

   Subscribe/Renew Journal


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.
User
Subscription Login to verify subscription
Notifications
Font Size

  • 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.


Abstract Views: 189

PDF Views: 0




  • A Brief Survey on Distributed Graph Algorithms For Shortest Distance

Abstract Views: 189  |  PDF Views: 0

Authors

V. Jenifer
KG College of Arts and Science, Coimbatore., India

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.

References