Journal of the ACM · 1979 · 196 citations · 6 references
ComputingComputer ScienceAlgorithmsComputational GeometryData StructuresAlgorithm AnalysisDirected Acyclic GraphsGraph AlgorithmsGraph Isomorphism
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,
6
Incidence matrices and interval graphs
D. R. Fulkerson, Oliver Gross · Pacific Journal of Mathematics · 1965 · 1.3K citations · Full text