Formal Language Constrained Path Problems
Formal Language Constrained Path Problems
In many path finding problems arising in diverse areas, such as
transportation science, Web search, Database queries and VLSI design
certain patterns of edge/vertex labels in the labeled graph being
traversed are allowed/preferred, while others are disallowed. Thus,
the feasibility of a path is determined by (i) its length (or cost)
under well known measures on graphs such as distance, and (ii) its
associated label. We model the set of acceptable label patterns as a
formal language. For example, in transportation systems with mode
options for a traveler to go from source to destination the mode
selection and destination patterns of an itinerary that a route will
seek to optimize can be specified by a formal language. A
prototypical problem considered is the following:
Formal Language Constrained Shortest/Simple Paths:
Given a labeled weighted (directed or undirected) graph G,
a source and a destination s and d, and a formal language L
(e.g. regular, context free, etc.) find a shortest (or simple)
path from s to d such that the label of the path is in L.
After a brief overview I will present a number of theoretical (lower
as well as upper bounds) and experimental results for such problems.
This is a joint work with Chris Barrett and Riko Jacob.