Speaker: Jean-François Baffier, JFLI & The University of Tokyo
Date: 19th April 2013
Place: room 202, Faculty of Science Bldg. 7, Hongo Campus, The University of Tokyo
A k-route channel is a communication path that goes through k edge-disjoints paths, providing a resistance up to k-1 edge failures. A k-route flow (a multiroute flow of routes) is sum of k-route channels according to the network capacities constraint. It provides a lower bound of the max-flow value in case of k-1 edge failures. A max-flow/min-cut duality theorem in the k-route context has been proven by Kishimoto and Takeuchi (93). This result can be easily extended to include node failures orr other variants of the multiroute flow problem. Given a network with one variable edge, we study the impact of the variation of the capacity of this edge on the multiroute flow in a general case (previous work has already treated the case of 1-route-flow and 2-route flow). For any integer k, we show that a max-k-flow solution is piecewise linear function (with at most k+1 breaking points). We provide a polynomial algorithm which us all the breaking points for a given source/sink pair. We also extend our approach to the case with any number of variable edges. Another approach, introduced by Lin (99), is to handle those failures by using stochastic-flow networks (with a probability of failure at nodes and arcs). To give efficient lower bounds and expected values of the flows, we will compare and combine parametric, multiroute, and stochastic flows.