The week's pick
Random Articles
Reseach Article
Least Cost Path Discovery over Graphs Defined for Large Volumes of Data Satisfying Node and Link Constraints
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 82 - Number 12 |
| Year of Publication: 2013 |
| Authors: Shom C. Abraham |
10.5120/14167-2267
|
Shom C. Abraham . Least Cost Path Discovery over Graphs Defined for Large Volumes of Data Satisfying Node and Link Constraints. International Journal of Computer Applications. 82, 12 ( November 2013), 15-18. DOI=10.5120/14167-2267
Abstract
Computing shortest paths in graphs is one of the most fundamental and well-studied problems in combinatorial optimization. Numerous real-world applications have stimulated research investigations in this area. Several applications include large graphs involving thousands of nodes, which we cannot assume to be fully loaded into memory. The problem is of much interest, when the nodes and edges have several constraints to be satisfied apart from being large, in the computation of shortest path. Conventional Dijkstra’s algorithm does not serve the purpose. There has not been much research done in this area, although some papers investigate the problem of large graphs.
References
- Ahuja, R. K. , Magnanti, T. L. and Orlin, J. B. (1993), Network Flows: Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ .
- Bellman, R. (1958), On a Routing Problem, Quart. Appl. Math. 16, 87-90.
- Cai, X. , Klocks, T. and Wong, C. K. (1997), Time-Varying Shortest Path Problems with Constraints, Networks, 29 , 141-149
- Cooke, K. L. and Halsey, E. (1966), The shortest route through a network with time-dependent internodal transit times, Journal of Mathematical Analysis and Applications, 14, 493-498 .
- Dijkstra, E. W. (1959), A Note on Two Problems in Connexion with Graphs, Numerishe Mathematic 1 , 269-271
- Dreyfus, S. E. (1969), An Appraisal of Some Shortest-Path Algorithms, Operations Research, 17, 395-412
- Floyd, R. W. (1962), Algorithm 97: shortest path. Comm. ACM 5345.
- Klein, P. N. and Subramanian, S. (1997), A Randomized Parallel Algorithm for Single-Source Shortest Paths, Journal of Algorithms, Vol. 25, No. 2, pp. 205-220
- Henzinger, M. R. , P. Klein, P. , Rao, S. and Sairam Subramanian (1997), Faster Shortest-Path Algorithms for Planar Graphs, Journal of Computer and System Science 55, 3-23.
- Cherkassky, B. V. , Goldberg, A. V. and Radzik, T. (1996), Shortest path algorithms: Theory and experimental evaluation, Mathematical Programming 73, 129-174.
Index Terms
Keywords