scientific article; zbMATH DE number 1769330

From MaRDI portal
Publication:4540086





This paper is the first in a series on the theory of balanced network flows. This theory provides a framework for the design and analysis of general matching algorithms. The authors define the general matching problem and introduce balanced flow networks. These allow general matching problems to be solved similar to how maximum flows allow the solution of bipartite matching problems. The necessary tools are developed in the paper. After notation and definitions of flow, maximum flow and balanced flow, flow augmentation is discussed. Results include a balanced flow decomposition theorem and an augmenting path theorem for balanced networks. Next the authors discuss lower capacity bounds. For efficient implementaion of balanced flow algorithms distance labels are used. These are needed to make the number of augmentations independent of arc capacities. Tenacity labels are used to identify arcs to be explored. Sections 9 and 10 discuss blossoms and nuclei. Main results here are the base identity for blossoms and nuclei. Computation of valid paths in a balanced network usually involve shrinking and expansion phases. The shrinking of blossoms, and properties thereof are presented. With these prerequisites properties of balanced network search algorithms are investigated. Two types of algorithms are considered: Tree growing (results on termination and path expansion are given) and an alternative concept that requires a more sophisticated search procedure. Here a structure theorem for minimum admissible paths is proved. For Part II and III, see the reviews Zbl 0999.90006 and Zbl 0999.90007.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4540086)