O(1) O ( 1 ) query time algorithm for all pairs shortest distances on permutation graphs
We present an algorithm for the all pairs shortest distance problem on permutation graphs. Given a permutation model for the graph on n  vertices, after O(n) O ( n ) preprocessing the algorithm will deliver answers to distance queries in O(1) O ( 1 ) time. In the EREW PRAM model, preprocessing can be accomplished in O(logn) O ( log n ) time with O(n) O ( n ) work. Where the distance between query vertices is k , a path can be delivered in O(k) O ( k ) time. The method is based on reduction to bipartite permutation graphs, a further reduction to unit interval graphs, and a coordinatization of unit interval graphs.
permutation graph bipartite permutation graph unit interval graph all pairs shortest paths