Title

Efficient Algorithms For All-Pairs Shortest Path Problem On Interval, Directed Path, And Circular-Arc Graphs

Abstract

Given a graph G=(V,E), with |V|=N and |E|=M, we present algorithms for the all-pairs shortest path (APSP) problem when G is an interval, directed path, or circular arc graph. In particular, we obtain the following results: (1) Given an interval graph or circular arc graph on N nodes with its respective interval or arc representation, we present an O(N)-time and space algorithm to preprocess the graph in such a way that the shortest path queries-queries asking for the distance between any pair of nodes in the graph-can be answered in constant time. (2) For the interval/circular arc/directed path graph G, we present an algorithm for an APSP problem with time and space complexity of O(N2) and O(N+M), respectively. The algorithm for interval graphs compares well with a previous algorithm by F. Gavril (1975) which solves the APSP problem with a time and space complexity of O(N2).

Publication Date

1-1-1993

Publication Title

Proceedings - ICCI 1993: 5th International Conference on Computing and Information

Number of Pages

31-35

Document Type

Article; Proceedings Paper

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ICCI.1993.315407

Socpus ID

0040540550 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0040540550

This document is currently not available here.

Share

COinS