Diameter Determination on Restricted Graph Families

摘要

Determining the diameter of a graph is a fundamental graph operation, yet no efficient (i.e. quadratic time) algorithm is known. In this paper, we examine the diameter problem on chordal and AT-free graphs and show that a very simple (linear time) 2-sweep Lex-BFS algorithm identifies a vertex of maximum eccentricity unless the given graph has a specified induced subgraph (it was previously known that a single Lex-BFS algorithm is guaranteed to end at a vertex that is within 1 of the diameter for chordal 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).