## 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**

**Abstract:**

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**

**Abstract:**

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 *P*_{e} 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 *Q*_{e} 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**

**Abstract:**

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.