✦ LIBER ✦

A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph

✍ Scribed by Mirchandani, Prakash

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 288 KB
Volume: 27
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199605)27:3<215::aid-net6>3.0.co;2-l

No coin nor oath required. For personal study only.

✦ Synopsis

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 algorithm is concise to state, intuitive to understand, and easy to implement. 0 7996 John Wiley & Sons, Inc.

📜 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 👁 1 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