A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs |
| |
Authors: | Louis Ibarra |
| |
Affiliation: | 1. College of Computing and Digital Media, DePaul University, 243 S. Wabash Ave., Chicago, IL, 60604, USA
|
| |
Abstract: | We present the first dynamic graph algorithm for recognizing interval graphs. The algorithm runs in O(nlog?n) worst-case time per edge deletion or edge insertion, where n is the number of vertices in the graph. The algorithm uses a new representation of interval graphs called the train tree, which is based on the clique-separator graph representation of chordal graphs. The train tree has a number of useful properties and it can be constructed from the clique-separator graph in O(n) time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|