An optimal algorithm to solve the all‐pair shortest path problem on interval graphs
R. Ravi, MADHAV V. MARATHE, Chandrasekharan Pandu Rangan · Networks · 1992
Abstract We present an O(n2) 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.