Flows over edge-disjoint mixed multipaths and applications

Abstract: For improving reliability of communication in communication networks, where edges are subject to failure, Kishimoto [Reliable flow with failures in a network, IEEE Trans. Reliability, 46 (1997) 308–315] defined a -reliable flow, for a given source-sink pair of nodes, in a network for , where no edge carries a flow more than a fraction of the total flow in the network, and proved a max-flow min-cut theorem with cut-capacites defined suitably. Kishimoto and Takeuchi in [A method for obtaining -reliable flow in a network, IECCE Fundamentals E-81A (1998) 776–783] provided an efficient algorithm for finding such a flow. When is an integer, say , Kishimoto and Takeuchi [On -route flows in a network, IEICE Trans. J-76-A (1993) 1185–1200 (in Japanese)] introduced the notion of a q-path flow. Kishimoto [A method for obtaining the maximum multi-route flows in a network, Networks 27 (1996) 279–291] proved a max-flow min-cut theorem for q-path flow between a given source-sink pair () of nodes and provided a strongly polynomial algorithm for finding a q-path flow from s to t of maximum flow-value. In this paper, we extend the concept of q-path flow to any real number . When q is fractional, we show that this general q-path flow can be viewed as a sum of some -path flow and some -path flow. We discuss several applications of this results, which include a simpler proof and generalization of a known result on wavelength division multiplexing problem. Finally we present a strongly polynomial, combinatorial algorithm for synthesizing an undirected network with minimum sum of edge capacities that satisfies (non-simultaneously) specified minimum requirements of q-path flow-values between all pairs of nodes, for a given real number . [Copyright &y& Elsevier]