Tech Report CS-89-21

A Data Structure for Arc Insertion and Regular Path Finding

Adam L. Buchsbaum, Paris C. Kanellakis and Jeffrey Scott Vitter

April 1989

Abstract:

If $G$ is a directed graph with labeled edges and $L$ is a fixed regular language, the {\em regular path problem}, given two nodes, $u$ and $v$, in $G$, is to find a path between $u$ and $v$ such that the labels on the arcs along that path form a string which is a member of $L$. We consider a dynamic version of this problem, adding arcs to and performing regular path queries on $G$ over $L$, and present a data structure that solves both problems in average time per operation linear in the number of nodes of the graph for any fixed regular language.

(complete text in pdf)