Optimal computation of shortest paths on doubly convex bipartite graphs

Optimal computation of shortest paths on doubly convex bipartite graphs

0.00 Avg rating0 Votes
Article ID: iaor20002980
Country: United Kingdom
Volume: 38
Issue: 3/4
Start Page Number: 1
End Page Number: 12
Publication Date: Aug 1999
Journal: Computers & Mathematics with Applications
Authors:
Keywords: computational analysis: parallel computers
Abstract:

An optimal parallel algorithm for computing all-pair shortest paths on doubly convex bipartite graphs is presented here. The input is a (0,1)-matrix with consecutive 1s in each of its rows and columns that represents a doubly convex bipartite graph. Our parallel algorithm runs in O(log n) time with O(n2/log n) processors on an EREW PRAM and is time-and-work-optimal. As a byproduct, we show that the problem can be solved by a sequential algorithm in O(n2) time optimally on any adjacency list or matrix representing a doubly convex bipartite graph. The result in this paper improves a recent work on the problem for bipartite permutation graphs which are properly contained in doubly convex bipartite graphs.

Reviews

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