|
|||||
|
|
An Optimal Algorithm to Solve the All-Pairs Shortest Paths Problem on Permutation Graphs |
|
| Authors: | Sukumar Mondal Madhumangal Pal Tapan K. Pal |
| Affiliation: | (1) Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore-, 721 102, India |
| Abstract: | In this paper we present an optimal algorithm to solve the all-pairs shortest path problem on permutation graphs with n vertices and m edges which runs in O(n2) time. Using this algorithm, the average distance of a permutation graph can also be computed in O(n2) time. |
| Keywords: | design of algorithms analysis of algorithms shortest paths average distance permutation graphs |
| 本文献已被 SpringerLink 等数据库收录！ | |