The shortest path with at most / nodes in each of the series/parallel clusters

✍ Scribed by Wen-Jui Li; H.-S. Jacob Tsao; Osman Ulular

• Publisher: John Wiley and Sons
• Year: 1995
• Tongue: English
• Weight: 777 KB
• Volume: 26
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230260410

✦ Synopsis

Abstract

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 /. The second problem considers two constraints: (i) a path cannot contain more than / 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.