Back to Search
Start Over
Diameter Determination on Restricted Graph Families.
- Source :
- Graph-Theoretic Concepts in Computer Science; 1998, p192-202, 11p
- Publication Year :
- 1998
-
Abstract
- 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). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540651956
- Database :
- Supplemental Index
- Journal :
- Graph-Theoretic Concepts in Computer Science
- Publication Type :
- Book
- Accession number :
- 32701084
- Full Text :
- https://doi.org/10.1007/10692760_16