An invertible transform for efficient string matching in labeled digraphs

Abhinav Nellore, Austin Nguyen, Reid F. Thompson

Let $G=(V,E)$ be a digraph where each vertex is unlabeled, each edge is labeled by a character in some alphabet $\Omega$, and any two edges with both the same head and the same tail…