CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

An Optimized All pair Shortest Paths Algorithm

by Vijay Shankar Pandey, Rajendra Kumar, Dr. P K Singh
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 2 - Number 3
Year of Publication: 2010
Authors: Vijay Shankar Pandey, Rajendra Kumar, Dr. P K Singh
10.5120/640-896

Vijay Shankar Pandey, Rajendra Kumar, Dr. P K Singh . An Optimized All pair Shortest Paths Algorithm. International Journal of Computer Applications. 2, 3 ( May 2010), 67-73. DOI=10.5120/640-896

@article{ 10.5120/640-896,
author = { Vijay Shankar Pandey, Rajendra Kumar, Dr. P K Singh },
title = { An Optimized All pair Shortest Paths Algorithm },
journal = { International Journal of Computer Applications },
issue_date = { May 2010 },
volume = { 2 },
number = { 3 },
month = { May },
year = { 2010 },
issn = { 0975-8887 },
pages = { 67-73 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume2/number3/640-896/ },
doi = { 10.5120/640-896 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T19:49:56.976386+05:30
%A Vijay Shankar Pandey
%A Rajendra Kumar
%A Dr. P K Singh
%T An Optimized All pair Shortest Paths Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 2
%N 3
%P 67-73
%D 2010
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper, we present an algorithm to compute all pairs optimized shortest paths in an unweighted and undirected graph with some additive error of at most 2.This algorithm can be extended for weighted graph also but it will not work for directed graph due to absence of commutative property. The algorithm runs in ??n5/2) times, where n is the number of vertices in the graph. This algorithm is much simpler than the existing algorithms. A study of upper bounds on the size of a maximal independent set of such graphs has been performed.

References
  1. Aingworth, D., Chekuri C., Indyk P., Motwani R., “Fast estimation of diameter and shortest paths (without matrix multiplication)”, SIAM Journal on Computing 28 (1999), 1167-1181.
  2. Alon N., Galil Z., Margalit O., “On the exponent of the all pairs shortest path problem”, Journal of Computer and System Sciences 54 (1997) 255 -262.
  3. Alon N., Naor M. Derandomization, “Witnesses for Boolean matrix multiplication and construction of perfect hast functions”, Algorithms 16 (1996), 434- 449.
  4. Baswana S., Goyal V., Sen S., “All-pairs nearly 2-approximate shortest-paths in o(n2 polylog n) time”, In STACS 2005: 22nd Annual Symposium on Theoretical Aspects of CS (2005), pp. 666- 679.
  5. Chvtal V., “A greedy heuristic for the set-covering problem”, Math. Oper. Res. 4 (1979), 233-235.
  6. Cohen E., Zwick U., “All-pairs small-stretch paths”, Journal of Algorithms 38 (2001), 335- 353.
  7. Coppersmtts D., Winoged S., “Matrix multiplication via arithmetic progression”, Journal of Symbolic Computation 9 (1990), 251-280.
  8. Cormen T., Stein C., Rivest R., Leiserson C., “Introduction to Algorithms”, PHI, 2001.
  9. Dijkstra, E., “A note on two problems in connection with graphs. Numeric Mathematic 1 (1959), 269-271.
  10. Dor D., Halperin S., Zwick U., “All pairs almost shortest paths”, SIAM Journal on Computing 29 (2000), 1740-1759.
  11. Fredmian M., “New bounds on the complexity of the shortest path problem”, SIAM Journal of computing 5 (1976), 83- 89.
  12. Galil Z., Margalit O., “Witnesses for Boolean matrix multiplication”, Journal of Complexity 9 (1993) 201- 221.
  13. Galil Z., Margalit O., “All pairs shortest paths for graph with small integer length edge”, Journal of Computer and System Science 54 (1997) 243-254.
  14. Hagerup T., “Improved shortest paths on the word ram”, In Proceedings of the 27th International Colloquium on Automata, Language and Programming (2000),pp. 61 -72.
  15. Halldorsson M., “Approximating the minimum maximal independence number”, Inf. Process. Lett. 46, 4 (1993), 169-172.
  16. Johnson D., “Efficient algorithms for shortest paths in sparse graphs”, Journal of the ACM 24 (1977), 1- 13.
  17. Karger D., Koller D., Phillips S., “Finding the hidden path: time bounds for all-pairs shortest paths”, SIAM Journal on Computing 22 (1993), 1199 -1217.
  18. Lovasz L., “On the ratio of optimal integral and fractional covers”, Discrete Math. 13 (1975), 383 -390.
  19. Mcgeoch G., “All-pairs shortest paths and the essential sub graph”, Algorithmic 13 (1995), 426-461.
  20. Pettie S., Ramachandran V., “Computing shortest paths with comparisons and additions”, In SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (2002), pp. 267- 276.
  21. Seidel R., “On the all-pairs-shortest-path problem in unweighted undirected graphs”, Journal of Computer and System Science 51 (1995), 400- 403.
  22. Takaoka T., “A new upper bound on the complexity of the all pairs shortest path problem”, Information Processing Letters 43 (1992), 195-199.
  23. Thorup M., “Undirected single-source shortest paths with positive integer weights in linear time”, Journal of the ACM 46 (1999), 362- 394.
  24. Thorup M., “Floats, integers, and single source shortest paths”, Journal of Algorithms 35 (2000), 189 -201.
Index Terms

Computer Science
Information Sciences

Keywords

Optimized Commutative Sub-Cubic Additive Error Multiplicative Error

Powered by PhDFocusTM