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)