Technical Report 359-1993

Title

Multicommodity Flows in Even, Planar Networks

Author

Karsten Weihe

Publication

Springer, Lecture Notes in Computer Science 762, Proc. 4th Intern. Symp. Algorithms and Computations (ISAAC '93), ed. K.W. Ng, P. Raghavan, N.V. Balasubramanian and F.Y.L. Chin, 1993, pp. 333-342

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

Abstract

We consider the problem of finding an integral multicommodity flow in a planar, undirected graph where all sources and all targets are on the boundary of the infinite face. Moreover, all capacities and all demands are integer and satisfy the evenness condition. The best algorithm known so far requires ` O(kn+n^2) time, where n` denotes the number of vertices and k the number of source- target pairs. In this paper, we introduce an algorithm that is based on a completely new approach and requires only ` O(kn)` time in the worst case, which is asymptotically optimal.