Skip to main content


eCommons@Cornell

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: Aug-1984
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR84-628
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

Files in This Item:

File Description SizeFormat
84-628.pdf6.57 MBAdobe PDFView/Open
84-628.ps1.34 MBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us