๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An optimal algorithm to solve the all-pair shortest path problem on interval graphs

โœ Scribed by R. Ravi; Madhav V. Marathe; C. Pandu Rangan

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
646 KB
Volume
22
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Solving the all-pair shortest path query
Solving the all-pair shortest path query problem on interval and circular-arc graphs
โœ Chen, Danny Z.; Lee, D. T.; Sridhar, R.; Sekharan, Chandra N. ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 118 KB ๐Ÿ‘ 3 views

In this paper, we study the following all-pair shortest path query problem: Given the interval model of an unweighted interval graph of n vertices, build a data structure such that each query on the shortest path (or its length) between any pair of vertices of the graph can be processed efficiently

A simpleO(n2) algorithm for the all-pair
A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph
โœ Mirchandani, Prakash ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 288 KB ๐Ÿ‘ 3 views

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n') algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our a

On the All-Pairs-Shortest-Path Problem i
On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs
โœ R. Seidel ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 318 KB

We present an algorithm, APD, that solves the distance version of the all-pairs-shortest-path problem for undirected, unweighted \(n\)-vertex graphs in time \(O(M(n) \log n)\), where \(M(n)\) denotes the time necessary to multiply two \(n \times n\) matrices of small integers (which is currently kno