scientific article; zbMATH DE number 1769330
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.
- scientific article; zbMATH DE number 842873
- Balancing Applied to Maximum Network Flow Problems
- Balanced network flows. III. Strongly polynomial augmentation algorithms
- A POLYNOMIAL ALGORITHM FOR THE MAXIMUM BALANCED FLOW PROBLEM WITH A CONSTANT BALANCING RATE FUNCTION
- scientific article; zbMATH DE number 653269
- Programming in networks and graphs. On the combinatorial background and near-equivalence of network flow and matching algorithms
- scientific article; zbMATH DE number 1101952
- scientific article; zbMATH DE number 1867228
- Balancing problems in acyclic networks
- Balanced network flows. V: Cycle-canceling algorithms.
- A \(0(| V | \cdot | E |)\) algorithm for maximum matching of graphs
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An algorithmic proof of Tutte's f-factor theorem
- Antisymmetrical Digraphs
- Balanced network flows. IV: Duality and structure theory.
- Balanced network flows. V: Cycle-canceling algorithms.
- Maximum matching and a polyhedron with 0,1-vertices
- Network Flow and Testing Graph Connectivity
- Path problems in skew-symmetric graphs
- Paths, Trees, and Flowers
- The Factors of Graphs
- TWO THEOREMS IN GRAPH THEORY
- Programming in networks and graphs. On the combinatorial background and near-equivalence of network flow and matching algorithms
- Optimal multilevel matching using network flows: an application to a summer reading intervention
- Balanced network flows. IV: Duality and structure theory.
- Balanced network flows. V: Cycle-canceling algorithms.
- Balanced network flows. VI: Polyhedral descriptions.
- Balanced network flows. VII: Primal-dual algorithms.
- scientific article; zbMATH DE number 653269 (Why is no real title available?)
- scientific article; zbMATH DE number 1769331 (Why is no real title available?)
- Balanced network flows. III. Strongly polynomial augmentation algorithms
- scientific article; zbMATH DE number 1867228 (Why is no real title available?)
- Balanced network flows. VIII. A revised theory of phase‐ordered algorithms and the O( $\bf\it\sqrt{n}m$ log(n2/m)/log n) bound for the nonbipartite cardinality matching problem
- scientific article; zbMATH DE number 842873 (Why is no real title available?)
- Maximum skew-symmetric flows
- Integer equal flows
- Graph factors and factorization: 1985--2003: a survey
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)