Contributed Session Tue.1.H 3002

Tuesday, 10:30 - 12:00 h, Room: H 3002

Cluster 23: Telecommunications & networks [...]

Flow and path problems


Chair: Clemens Thielen



Tuesday, 10:30 - 10:55 h, Room: H 3002, Talk 1

Clemens Thielen
Maximum flows with minimum quantities

Coauthor: Stephan Westphal


We consider a variant of the maximum flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound (a minimum quantity). This problem has recently been shown to be weakly NP-complete even on series-parallel graphs.

We show that it is strongly NP-hard to approximate the maximum flow problem with minimum quantities (MFPMQ) on general graphs within any positive factor. On series-parallel graphs, however, we present a pseudo-polynomial dynamic programming algorithm for the problem.
Moreover, we show that the problem is still weakly NP-complete on general graphs for the case that the minimum quantity is the same for each arc in the network and we present a (2-1⁄ λ )-approximation algorithm for this case, where λ denotes the common minimum quantity of all arcs.



Tuesday, 11:00 - 11:25 h, Room: H 3002, Talk 2

Marco Senatore
The online replacement path problem

Coauthor: David Adjiashvili


We study a natural online variant of the replacement path problem. The replacement path problem asks to find for a given graph G = (V,E), two designated vertices s,t ∈ V and a shortest s-t path P in G, a replacement path Pe for every edge e on P. We adapt this problem to deal with the natural scenario that the identity of the failed edge only becomes available when the routing mechanism tries to cross the edge. This situation is motivated by applications in distributed networks, where information about recent changes in the network is only stored locally, and fault-tolerant optimization, where an adversary tries to delay the discovery of the materialized scenario as much as possible. Consequently, we define the online replacement path problem, which asks to find a nominal s-t path Q and detours Qe for every edge on Q, such that the worst-case arrival time at the destination is minimized. Our main contribution is a label setting algorithm solving the problem in undirected graphs in time O(m log n) and linear space for all sources and a single destination. We also present algorithms for extensions of the model to any bounded number of failed edges.



Tuesday, 11:30 - 11:55 h, Room: H 3002, Talk 3

Joao Paulo Araujo
An algorithm for the multi-terminal maximum flow

Coauthors: Pascal Berthomé, Madiagne Diallo, Fernanda Raupp


In the context of network flows, the multi-terminal maximum flow problem is an extension of the well known single source-single terminal maximum flow problem. In the multi-terminal case, the maximum flow is calculated between all pairs of nodes. Clearly, considering a symmetric network with n nodes, this problem can be solved by applying a maximum flow algorithm n(n-1)/2 times, whereas the traditional methods can solve it with only n-1 applications. This work seeks to elaborate an algorithm able to solve the multi-terminal maximum flow problem with a computational complexity lower than the existing methods. The recent theory of sensitivity analysis, which studies the influence of an edge capacity variation on the multi-terminals maxima flows, is employed on the development of the algorithm. Techniques of the traditional methods, such as the contraction of nodes, are also part of the proposed method. Finally, the algorithm is computationally tested with all combined feature variations and heuristics. For a given instance, the algorithm showed efficiency very close to the traditional methods.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.