## Intersection graph algorithmsAn 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Definitions and Background | 4 |

Directed Path Hypergraphs and Partial Path Trees | 23 |

Algorithms on Partial Path Trees | 42 |

3 other sections not shown

### Common terms and phrases

abort Above(x,c Add-Edge algorithm for finding Assume bijection breadth-first search characteristic node child chordal graphs clique hypergraph CONN(x connector CONSISTENT{Z deepest vertex definition 3-4 deleting directed path graphs directed path hypergraphs directed path tree directed tree disjoint edge in E(H edge intersecting edge labelled isomorphism Figure Find-Path-Tree-with-Root Find-PPT Find-PPT-with-Root graph G graph isomorphism H and H H Below(x H to H H with root Hamiltonian circuits hypercycle induced subgraph induces a directed induces a path intersection graph interval graphs lemma line 45 linear time algorithm maximal cliques nonempty NP-complete null tree oriented inwards Otherwise parent partial path tree path tree problem perfect elimination scheme PPT for H PPT for H[E PPT's PQR trees PQRLabel proc Procedure Proof of theorem proper ancestor proper descendants run in linear sequence set of vertices simple hyperpath simplifies subset theorem 4-9 tree for H tree with root ujfc unrelated descendants ZV,AV