No label defined (Q4540086)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1769330
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1769330

      Statements

      21 July 2002
      0 references
      matching problems
      0 references
      network flows
      0 references
      balanced flow networks
      0 references
      augmentation
      0 references
      blossoms
      0 references
      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.
      0 references

      Identifiers