Diameter determination on restricted graph families

AbstractDetermining the diameter of a graph is a fundamental graph operation, yet no efficient (i.e. linear or quadratic time) algorithm is known. In this paper, we examine the diameter problem on chordal graphs and AT-free graphs and show that a very simple (linear time) 2-sweep LexBFS algorithm identifies a vertex of maximum eccentricity unless the given graph has a specified induced subgraph (it was previously known that a single LexBFS algorithm is guaranteed to end at a vertex that is within 1 of the diameter for chordal graphs and AT-free graphs). As a consequence of the forbidden induced subgraph result on chordal graphs, our algorithm is guaranteed to work optimally for directed path graphs (it was previously known that a single LexBFS algorithm is guaranteed to work optimally for interval graphs)