IJSRSET calls volunteers interested to contribute towards the scientific development in the field of Science, Engineering and Technology

Home > IJSRSET1625115                                                     

Survey on Mining Shortest Path in Directed and Dynamic Graphs


K. Sangeetha, B. Kaleeswari, K. Anitha, G. Boopathi
  • Abstract
  • Authors
  • Keywords
  • References
  • Details
Calculating the shortest path in larger graph is one of the major problems in graph theory. There are some algorithms available for finding the shortest paths in graph. But those algorithms are not efficient for finding the shortest path in larger directed graph. So we are going to propose a new algorithm for finding the shortest path in directed and dynamic graph. The data reduction technique proxies are used for mining the shortest path in graph. The Dijktra’s algorithm is used for finding the shortest path in early graph theory. But it is not efficient for larger graphs. So we are going to create a new algorithm by combining the methods of Dijktra’s and data reduction techniques. By using this algorithm we are going to find the shortest path in directed and dynamic graphs.

K. Sangeetha, B. Kaleeswari, K. Anitha, G. Boopathi

Graph, Shortest Path, Data Reduction Technique, Proxies

  1. Lappas, K. Liu, and E. Terzi, "Finding a team of experts in social networks," in Proc. 15th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2009, pp. 467–476.
  2. Potamias, F. Bonchi, C. Castillo, and A. Gionis, "Fast shortest path distance estimation in large networks," in Proc. ACM Int. Conf. Inf. Knowl. Manage., 2009, pp. 867–876.
  3. D. Sarma, S. Gollapudi, M. Najork, and R. Panigrahy, "A sketch-based distance oracle for web-scale graphs," in Proc. 3rd ACM Int. Conf. Web Search Data Mining, 2010, pp. 401–410.
  4. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, vol. 1, pp. 269–271, 1959.
  5. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. In SODA, pages 937–946, 2002.
  6. Cheng and J. X. Yu. On-line exact shortest distance query processing. In EDBT, pages 481–492, 2009.
  7. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Hierarchical hub labelings for shortest paths. In ESA, pages 24–35. 2012.
  8. Jin, N. Ruan, Y. Xiang, and V. Lee. A highway-centric labeling approach for answering distance queries on large sparse graphs. In SIGMOD, pages 445–456, 2012.
  9. Wei. Tedi: efficient shortest path query answering on graphs. In SIGMOD, pages 99–110, 2010.
  10. Akiba, C. Sommer, and K. Kawarabayashi. Shortest-path queries for complex networks: exploiting low tree-width outside the core. In EDBT, pages 144–155, 2012.
  11. Chen, C. Sommer, S.-H. Teng, and Y. Wang. A compact routing scheme and approximate distance oracle for power-law graphs. TALG, 9(1):4:1–26, 2012.
  12. E. J. Newman, S. H. Strogatz, and D. J. Watts. Random graphs with arbitrary degree distributions and their applications. Physical Review E, 64(2):026118 1–17, 2001
  13. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts. Network robustness and fragility: Percolation on random graphs. Physical Review Letters, 85:5468–5471, 2000.
  14. Cheng, Y. Ke, S. Chu, and C. Cheng, "Efficient processing of distance queries in large graphs: A vertex cover approach," in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2012, pp. 457–468.
  15. H. M€ohring, H. Schilling, B. Sch€utz, D. Wagner, and T. Willhalm, "Partitioning graphs to speedup Dijkstra’s algorithm," ACM J. EA, vol. 11, pp. 1–29, 2006.
  16. D. Zhu, H. Ma, X. Xiao, S. Luo, Y. Tang, and S. Zhou, "Shortest path and distance queries on road networks: Towards bridging theory and practice," in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2013, pp. 857–868.
  17. Arz, D. Luxen, and P. Sanders, "Transit node routing reconsidered," in Proc. 12th Int. Symp. Exp. Algorithms, 2013, pp. 55–66.
  18. Diestel, Graph Theory. New York, NY, USA: Springer, 2005.
  19. E. Hopcroft and R. E. Tarjan, "Efficient algorithms for graph manipulation h(algorithm 447)," Commun. ACM, vol. 16, no. 6, pp. 372–378, 1973.

Publication Details

Published in : Volume 2 | Issue 5 | September-October - 2016
Date of Publication Print ISSN Online ISSN
2016-10-31 2395-1990 2394-4099
Page(s) Manuscript Number   Publisher
431-437 IJSRSET1625115   Technoscience Academy

Cite This Article

K. Sangeetha, B. Kaleeswari, K. Anitha, G. Boopathi, "Survey on Mining Shortest Path in Directed and Dynamic Graphs", International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 2, Issue 5, pp.431-437, September-October-2016.
URL : http://ijsrset.com/IJSRSET1625115.php