An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs

An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs

0.00 Avg rating0 Votes
Article ID: iaor20043288
Country: Netherlands
Volume: 2
Issue: 1
Start Page Number: 57
End Page Number: 65
Publication Date: Jan 2003
Journal: Journal of Mathematical Modelling and Algorithms
Authors: , ,
Keywords: graphs
Abstract:

In this paper we present an optimal algorithm to sove 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.

Reviews

Required fields are marked *. Your email address will not be published.