Minimum-Cost Multiple Paths Subject to Minimum Link and Node Sharing in a Network
In communication networks, multiple disjoint communication paths are desirable for many applications. Such paths, however, may not exist in a network. In such a situation, paths with minimum link and/or node sharing may be considered. This paper addresses the following two related fundamental questions. First, in case of no solution of disjoint multiple paths for a given application instance, what are the criteria for finding the best solution in which paths share nodes and/or links? Second, if we know the criteria, how do we find the best solution? We propose a general framework for the answers to these two questions. This framework can be configured in a way that is suitable for a given application instance. We introduce the notion of link shareability and node shareability and consider the problem of finding minimum-cost multiple paths subject to minimum shareabilities (MCMPMS problem). We identify 65 different link/node shareability constraints, each leading to a specific version of the MCMPMS problem. In a previously published technical report, we prove that all the 65 versions are mutually inequivalent. In this paper, we show that all these versions can be solved using a unified algorithmic approach that consists of two algorithm schemes, each of which can be used to generate polynomial-time algorithms for a set of versions of MCMPMS. We also discuss some extensions where our modeling framework and algorithm schemes are applicable.
multiple paths network algorithm complexity disjoint paths graph network flow network planning protection protocol reliability routing survivability