Loading...
Please wait, while we are loading the content...
Similar Documents
An Efficient Algorithm for All Pair Shortest Paths
| Content Provider | Semantic Scholar |
|---|---|
| Author | Singh, Pankaj K. Kumar, Rajendra Pandey, Vijay Shankar |
| Copyright Year | 2010 |
| Abstract | In this paper, an all pairs optimized shortest path algorithm is presented for 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 run time of the algorithm is of order O(n5/2), where n is the number of vertices present 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 also been discussed. Index Terms—Additive Error, Commutative, Multi-plicative Error, Optimized. |
| Starting Page | 984 |
| Ending Page | 991 |
| Page Count | 8 |
| File Format | PDF HTM / HTML |
| DOI | 10.7763/IJCEE.2010.V2.263 |
| Alternate Webpage(s) | http://www.ijcee.org/papers/263-E309.pdf |
| Alternate Webpage(s) | https://doi.org/10.7763/IJCEE.2010.V2.263 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |