Algorithms for finding paths with multiple constraints

Abstract

Let G = (V, E) be a graph with weight function w:E rightarrow Z+ and length function l:E /rightarrow Z+. The problem of determining for v1, V2 /in V whether there is a path from v1 to v2 with weight at most W and length at most L is NP‐complete. This paper gives two approaches to meeting or approximating the length and weight constraints. The first approach is to use a pseudopolynomial‐time algorithm which determines whether a path meets the constraints. Its running time is O (n5 b log nb) where n = |V| and b is the largest length or weight. If tables with O (n3b) entries are kept then all instances of multiple constraints may be decided. Table size may be substantially decreased if one is willing to tolerate incorrect answers to rare instances. The algorithm is suitable for distributed execution. In the second approach, an objective function is defined which evaluates a path's distance from meeting the constraints. Polynomial‐time algorithms attempt to find good paths in terms of the objective function. One algorithm is at most 1.62 times worst than optimal. A notion of “average worst‐case behavior” is defined. The algorithm's “average” behavior is 1.51 times worse than optimal. Copyright © 1984 Wiley Periodicals, Inc., A Wiley Company