Premium
Algorithms for finding paths with multiple constraints
Author(s) -
Jaffe Jeffrey M.
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140109
Subject(s) - function (biology) , combinatorics , path (computing) , weight function , mathematics , running time , minimum weight , graph , time complexity , binary logarithm , path length , algorithm , computer science , discrete mathematics , statistics , computer network , evolutionary biology , biology , programming language
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 v 1 , V 2 /in V whether there is a path from v 1 to v 2 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 ( n 5 b log nb ) where n = |V| and b is the largest length or weight. If tables with O ( n 3 b ) 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.