Fast approximation algorithms for routing problems with hop-wise constraints

Given a graph G(N,A) with a cost (or benefit) and a delay on each arc, the constrained routing problem (CRP) aims to find a minimum-cost or a maximum-benefit path from a given source to a given destination node, subject to an end-to-end delay constraint. The problem (with a single constraint) is NP-hard, and has been studied by many researchers who found fully polynomial approximation schemes (FPAS) for this problem. The current paper focuses on a generalized CRP version, CRP with hop-wise constraints (CRPH). In the generalized version, instead of one constraint there are up to n−1 special-type constraints, where n is the number of nodes. An FPAS based on interval partitioning is proposed for both the minimization and the maximization versions of CRPH. For G(N,A) with n nodes and m arcs, the complexity of the algorithm is O(mn 2/e).