Theory and Practice

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. In this setting, many practical problems can be equivalently cast as multi-constrained shortest/simple path problems. An illustrative example is the problem of finding fastest paths in time dependent networks that have piecewise linear link traversal functions with the additional constraint that the label of the path belongs to a user specified regular grammar. The talk will focus on the modeling power, robustness to modifications (extensibility) and computational complexity of solving such multi-constrained routing problems. The theoretical results, modeling applications and the experimental data obtained suggests that the formalism allows interesting compromises between the conflicting goals mentioned above. In order to evaluate our ideas in a practical setting, I will report on preliminary computational experience on the performance of the proposed algorithms. This experience was gained in the context of the ongoing TRANSIMS (Transportation Analysis and Simulation System) project at the Los Alamos National Laboratory. |