×

Algorithms for finding paths with multiple constraints. (English) Zbl 0532.68068

Summary: Let \(G=(V,E)\) be a graph with weight function w: \(E\to {\mathbb{Z}}^+\) and length function l: \(E\to {\mathbb{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 \(0(n^ 5b \log nb)\) where \(n=| V|\) and b is the largest length or weight. If tables with \(0(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 rate 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 worse than optimal. A notion of ”average worst-case behavior” is defined. The algorithm’s ”average” behavior is 1.51 times worse than optimal.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] , and , The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974).
[2] Tables of Integrals and Other Mathematical Data. MacMillan, NY (1961).
[3] and , Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979). · Zbl 0411.68039
[4] ”Algorithms for finding paths with multiple constraints”. IBM RC 8205, April, 1980.
[5] and , ”A failsafe distributed routing protocol”. IEEE Trans. Comm. COM-27 (1979) 1230–1237.
[6] Tajibnapis, Comm. ACM 20 pp 477– (1977)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.