A Distributed Context-Free Language Constrained Shortest Path Algorithm
Charles B. Ward, Nathan M. Wiegand, Phillip G. Bradford · 2008
Formal language constrained shortest path problems are concerned with finding shortest paths in labeled graphs. These labeled paths have the constraint that the concatenation of labels along a path constitute a valid string in some formal language \Lambda over alphabet \Sigma. These problems are well studied where the formal language is regular or context-free, and have been used in a variety of applications ranging from databases, to transportation planning, to programming languages. Barrett, Jacob, and Marathe's best algorithm for the context-free language constrained path problem runs in O(|V|^3|N| |P|) time, where N is the set of non-terminals for the input grammar and P is the set of productions (expressed in Chomsky Normal Form). We present a work and time efficient distributed version of this algorithm that may be distributed on up to O(|V| |N|) nodes.