TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1989

COGA 5-Wheel

Inhalt

zur Navigation

Preprints 1989

An Incremental Linear-Time Algorithm to Recognize Interval Graphs
Zitatschlüssel Report-187-1988
Autor Norbert Korte and Rolf H. Möhring
Seiten 68-81
Jahr 1988
Journal SIAM J. Computing, 1989
Jahrgang 18
Nummer 187
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe