
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 satisfy the so-called evenness condition. The best algorithm known so far requires ${\cal 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 is asymptotically optimal, that is, requires only ${\cal O}(kn)$ time in the worst case.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
