Technical Report 187-1988
- Title
- An Incremental Linear-Time Algorithm to Recognize Interval Graphs
- Authors
- Norbert Korte and Rolf H. Möhring
- Publication
- SIAM J. Computing, vol. 18, 1989, pp. 68-81
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
- Classification
-
not available
- Keywords
-
not available
-
The fastest known algorithm for recognizing graphs iteratively manipulates the system of all maximal cliques of the given graph in a rather complicated way in order to construct a consecutive arrangement (more precisely: a tree representation of all possible such consecutive arrangements). We present a much simpler algorithm which uses a related, but much more informative tree representation of interval graphs. This tree is constructed in an incremental fashion by adding vertices to the graph in a predefined order such that adding a vertex u takes O(|Adj(u)| +1) amortized time.