A Linear Time Algorithm for Deciding Interval Graph Isomorphism

George S. Lueker, Kellogg S. Booth

Journal of the ACM · 1979 · 196 citations · 6 references

DOIFull text

Open access

Concepts

Abstract

A graph is an interval graph tf and only if each of Its verttces can be associated with an interval on the real hne m such a way that two vertices are adjacent m the graph exactly when the corresponding mtervals have a nonempty mtersectmn An effictent algonthrn for testing tsomorpinsm of interval graphs ts unplemented using a data structure called a PQ-tree. The algorithm runs m O(n + e) steps for graphs having n vemces and e edges It is shown that for a somewhat larger class of graphs, namely the chordal graphs, lsomorpinsm is as hard as for general graphs KEY WORDS AND PHRASES graph tsomorpinsm algonthms,

References

6