eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/6467
Title:  Intersection Graph Algorithms 
Authors:  Dietz, Paul F. 
Keywords:  computer science technical report 
Issue Date:  Aug1984 
Publisher:  Cornell University 
Citation:  http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR84628 
Abstract:  An intersection graph for a set of sets $C$ is a graph $G$ together with a bijection from the vertices of $G$ to $C$ such that distinct vertices in $G$ are adjacent if and only if their images under this bijection intersect. Of particular interest have been the classes of chordal graphs, the intersection graphs of sets of subtrees of a tree, and interval graphs, the intersection graphs of sets of intervals of the real line. I examine another class of intersection graphs, the class of directed path graphs: intersection graphs of sets of paths in a directed tree. This class properly contains the class of interval graphs, and is properly contained by the class of chordal graphs. I give a linear time algorithm for recognizing directed path graphs and for constructing intersection representations, and a polynomial time algorithm for deciding directed path graph isomorphism. Both algorithms use a data structure called a partial path tree, which is a kind of skeletal representation of the clique hypergraph of a directed path graph. I present linear time algorithms for finding partial path trees with specific roots and for finding partial path trees with arbitrary roots. I prove that partial path trees with identical roots are identical. Using this fact I develop a polynomial time algorithm for directed path graph isomorphism. 
URI:  http://hdl.handle.net/1813/6467 
Appears in Collections:  Computer Science Technical Reports

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
