| [home] - [up] |
Abstract: For flows in undirected graphs, the famous MaxFlow-MinCut Theorem of Ford and Fulkerson can be generalized to the case of 2-commodity flows: Hu's 2-commodity flow theorem states that the cut condition implies the existence of a feasible 2-commodity flow. Hu also showed that if all capacities are integer, there is a half-integer 2-commodity flow. Generally, an integer 2-commodity flow need not exist. In fact, the undirected integer 2-commodity flow problem is NP-complete. The first part of the lecture gives a review of the mentioned results.
In the second part of this lecture we present a recent application of Hu's 2-commodity flow theorem in the context of network design. In the "virtual private network design" problem we are given a weighted undirected graph. Each node in the network has associated thresholds on the amount of flow that it can send to and receive from the network. The problem then is to reserve capacities at minimum cost and to specify paths between every ordered pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths. We discuss recent approximation results for this problem which have been jointly obtained with Fritz Eisenbrand, Fabrizio Grandoni, and Gianpaolo Oriolo.
Colloquium - 16:00
Abstract: We study a special case of the general set cover problem, namely, a relation between the number k of edge-disjoint odd cycles and the minimum number t of edges meeting all odd cycles in the class of planar graphs. Obviously, k≤t for each planar graph. A connection to a so-called T-join problem and a polynomial time algorithm for maxcut problem for the class of planar graphs is explored. As an application of linear programming duality, we derive the inequality t≤2k which is the best possible upper bound on t in terms of k as shown by examples of 3-connected planar graphs for which the equality holds. Our bound improves a previous fast-growing upper bound derived by Berge and Reed.