The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 24 NO.5 / (1995))
Flow in Planar Graphs with Multiple Sources and Sinks
Gary L. Miller, Joseph (Seffi) Naor,
Pages. 1002-1017
Abstract The problem of maximum flow in planar graphs has always been investigated under the assumption that there is only one source and on sink. Here we consider the case where there are many sources and sinks (single commodity) in a directed planar graphs. An algorithm for the case when the demands of the sources and sinks are fixed and given in advance is presented. The algorithm can be implemented efficiently sequentially and in parallel, and its complexity is dominated by the complexity of computing all shortest paths from a single source in a planar graph. If the demands are not known, an algorithm for computing the maximum flow is presented for the case where the number of faces that contain sources and sinks is bounded by a slowly growing function. Our result places the problem of computing a perfect matching in a planar bipartite graph in NC and
improves a previous parallel algorithm for the case of a single source, single sink in a planar directed (and undirected) graph, both in terms of processor bounds and its simple presentation.
Contents 1. Introduction
2. Previous results in planar flow
3. Terminology and preliminaries
3.1. Flow in planar graphs
4. Computing circulations
5. Applications of the circulation algorithm
5.1. Computing the flow function for fixed demands
5.2. Finding a perfect matching
5.3. Planar maximum flow with a single source and sink
6. Maximum flow on the disk
6.1. Maximum flow on the disk with positive capacities and zero demands
6.2. Maximum flow on disk with negative capacities
7. Maximum flow for a bounded number of faces containing sources and sinks
Key words planar graphs, flow, circulation.
Mathmatical Subject Classification 68R10, 05C38, 90B10, 90C35, 90