Browse Prior Art Database

A LINEAR TIME ALGORITHM FOR DECIDING INTERVAL GRAPH ISOMORPHISM

IP.com Disclosure Number: IPCOM000128322D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 17 page(s) / 49K

Publishing Venue

Software Patent Institute

Related People

George S. Lueker: AUTHOR [+4]

Abstract

A-graph is an interval graph it and only if each of its vertices can be associated with an interval on the reai line in such a way tnat two vertices are adjacent in the graph exactly when the corresponding intervals nave a nonempty intersection. An etficient algorithm for testing isomorphism of interval graphs is implemented using a data structure called a PQ-tree. The algorithm runs in O(n + e) steps for graphs having n vertices and e edges. It is shown that for a somewhat larger class of graphs, namely the chordal graphs, isomorphism is as hard as for general graphs.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 17

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A LINEAR TIME ALGORITHM FOR DECIDING INTERVAL GRAPH ISOMORPHISM

by

George S. Lueker Kellogg S. Booth

Technical Report #109

Department of Information and Computer Science University of California, Irvine Irvine, California 92717

A LINEAR TIME ALGORlThM FOR DECIDING INTERVAL GRAPH ISOMORPHISM by George
S. Luekej,+ and Kellogg S. Booth++

+Supported by the National Science Foundation under Grant MCS77-04410 at Irvine and by NSF Grant GJ-1052 at Princeton University

++Supported by the National Research Council of Canada under Grant No. A-4307 at Waterloo and by the U.S. Energy Research and Development Agency under Contract No. W-7405-Eng- 48 at Lawrence Livermore Laboratory

Authors' addresses:

George S. Lueker Department of Information and Computer Science University of California, Irvine Irvine, California 92717

heilogg S. Bootn Department of Computer Science University of Waterloo Waterloo, Ontario, Canada N2L 3G1

Abstract

A-graph is an interval graph it and only if each of its vertices can be associated with an interval on the reai line in such a way tnat two vertices are adjacent in the graph exactly when the corresponding intervals nave a nonempty intersection. An etficient algorithm for testing isomorphism of interval graphs is implemented using a data structure called a PQ-tree. The algorithm runs in O(n + e) steps for graphs having n vertices and e edges. It is shown that for a somewhat larger class of graphs, namely the chordal graphs, isomorphism is as hard as for general graphs.

1 Introduction.

Let G be a graph; let V be its set of vertices and let E be its set of edges. Let n be the number of vertices and e be the number of edges. G is said to be the intersection grapt of a family of sets F JS if there is a one-to-one correspondence between V and F such two vertices are adjacent if and only if the corresponding sets have 6 nonempty intersection. For example, G is said to be an interval (Iraph it it is the intersection graph of a family of intervals on tne real line, that is, it it

University of California, Irvine Page 1 Dec 31, 1978

Page 2 of 17

A LINEAR TIME ALGORITHM FOR DECIDING INTERVAL GRAPH ISOMORPHISM

is possible to set up a one-to-one correspondence between its vertices and a set of intervals on the real line such that two vertices are adjacent it and only it the corresponding intervals have a nonempty intersection. The set of intervals is called an intersection model tor G. Figure I gives an example of an interval graph and its intersection model. The problem of characterizing such graphs was posed by Haj6s [8]. Since then a number of interesting applications for interval graphs have been found; [15] contains a survey of these applications. A somewhat larger class of graphs is the class of chordal graphs. If C is a cycle in a graph G, C is said to have a chord if there is an edge in G, other than the edges of the cycle, which connects two vertices of...