Premium
An optimal algorithm to solve the all‐pair shortest path problem on interval graphs
Author(s) -
Ravi R.,
Marathe Madhav V.,
Pandu Rangan C.
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220103
Subject(s) - shortest path problem , combinatorics , longest path problem , mathematics , vertex (graph theory) , interval graph , interval (graph theory) , indifference graph , pathwidth , algorithm , graph , discrete mathematics , line graph
We present an O ( n 2 ) time‐optimal algorithm for solving the unweighted all‐pair shortest path problem on interval graphs, an important subclass of perfect graphs. An interesting structure called the neighborhood tree is studied and used in the algorithm. This tree is formed by identifying the successive neighborhoods of the vertex labeled last in the graph according to the IG‐ordering.