Survey on Mining Shortest Path in Directed and Dynamic Graphs
Keywords:
Graph, Shortest Path, Data Reduction Technique, ProxiesAbstract
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.
References
- 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.
- 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.
- 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.
- W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, vol. 1, pp. 269–271, 1959.
- Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. In SODA, pages 937–946, 2002.
- Cheng and J. X. Yu. On-line exact shortest distance query processing. In EDBT, pages 481–492, 2009.
- Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. Hierarchical hub labelings for shortest paths. In ESA, pages 24–35. 2012.
- 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.
- Wei. Tedi: efficient shortest path query answering on graphs. In SIGMOD, pages 99–110, 2010.
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- 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.
- Arz, D. Luxen, and P. Sanders, "Transit node routing reconsidered," in Proc. 12th Int. Symp. Exp. Algorithms, 2013, pp. 55–66.
- Diestel, Graph Theory. New York, NY, USA: Springer, 2005.
- E. Hopcroft and R. E. Tarjan, "Efficient algorithms for graph manipulation h(algorithm 447)," Commun. ACM, vol. 16, no. 6, pp. 372–378, 1973.
Downloads
Published
Issue
Section
License
Copyright (c) IJSRSET
This work is licensed under a Creative Commons Attribution 4.0 International License.