Networks

Solving the all‐pair shortest path query problem on interval and circular‐arc graphs

Journal Article

  • Author(s): Danny Z. Chen, D. T. Lee, R. Sridhar, Chandra N. Sekharan
  • Article first published online: 07 Dec 1998
  • DOI: 10.1002/(SICI)1097-0037(199807)31:4<249::AID-NET5>3.0.CO;2-D
  • Read on Online Library
  • Subscribe to Journal

Abstract

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 (both sequentially and in parallel). We show that, after sorting the input intervals by their endpoints, a data structure can be constructed sequentially in O(n) time and O(n) space; using this data structure, each query on the length of the shortest path between any two intervals can be answered in O(1) time, and each query on the actual shortest path can be answered in O(k) time, where k is the number of intervals on that path. Furthermore, this data structure can be constructed optimally in parallel, in O(log n) time using O(n/log n) CREW PRAM processors; each query on the actual shortest path can be answered in O(1) time using k processors. Our techniques can be extended to solving the all‐pair shortest path query problem on circular‐arc graphs, both sequentially and in parallel, in the same complexity bounds. As an immediate consequence of our results, we improve by a factor of n the space complexity of the previously best‐known sequential all‐pair shortest path algorithm for unweighted interval graphs. © 1998 John Wiley & Sons, Inc. Networks 31: 249–258, 1998

Related Topics

Related Publications

Related Content

Site Footer

Address:

This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.