THE SHORTEST-PATH WITH AT MOST L-NODES IN EACH OF THE SERIES/PARALLEL CLUSTERS

We study two related constrained shortest path problems in which the nodes are partitioned into series/ parallel clusters. These and many other constrained shortest path problems occur in optimizing the layout of private networks embedded in a larger telecommunications network. The first problem deals with a situation in which, in addition to each edge being assigned a nonnegative integer weight, each node is also assigned a nonnegative integer weight, and the constraint on the path is that the total node weight incurred within each cluster should not exceed a given nonnegative integer I. The second problem considers two constraints: (i) a path cannot contain more than I nodes in one cluster and (ii) a path must traverse through at least one of a given set of special nodes in each of the traversed clusters. We propose efficient exact algorithms for solving both problems. Numerical examples are also provided. (C) 1995 John Wiley & Sons, Inc.