A decomposition algorithm for multi-terminal network flows
There is a well-known solution to the problem of computing the maximum flow between all terminals in a graph of m undirected edges and n vertices. It has been provided by Hu in a classical paper, and requires n-1 maximum flow calculations resulting in the so-called cut tree for the network. Assuming that \(m=O(n^ 2)\), each maximum flow calculation can be done in \(O(n^ 3)\) time, and the total complexity of the algorithms is \(O(n^ 4).\) This may be too large for large networks. In this case, the authors propose another method that relies on the fact that large networks can often be decomposed into components, for which maximum flow calculations can be made more efficiently. The components in question are the so- called tri-connected components, in the sense defined by \textit{J. E. Hopcroft} and \textit{R. E. Tarjan} [SIAM J. Computing 2, 135--158 (1973; Zbl 0281.05111)]. The algorithm is as follows. (1) Decompose the network into its tri-connected components. (2) From these components, construct a rooted tree, called the component tree. (3) For each component, starting from the leaves of the tree, compute the maximum flow, using only the edges in the component. (4) Proceeding upwards, find the corresponding cut-tree for the root. Then, traverse the component tree downward again to obtain the cut-tree of all the vertices. The paper gives a description of the decomposition algorithm, as well as an expression for its complexity. If the network has p tri-connected components of size O(n/p), then it is \(O(n^ 4/p^ 3+n^ 2)\), a substantial improvement over the classical method when p is large.
- Faster network algorithms based on graph decomposition
- Very Simple Methods for All Pairs Network Flow Analysis
- scientific article; zbMATH DE number 910923
- A decomposition algorithm to determine the maximum flow in a generalized network
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- A decomposition algorithm for multi-terminal network flows
- A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
- A simple version of Karzanov's blocking flow algorithm
- An O(IVI^3) algorithm for finding maximum flows in networks
- An Efficient Heuristic Procedure for Partitioning Graphs
- Circular Cuts in a Network
- Depth-First Search and Linear Graph Algorithms
- Dividing a Graph into Triconnected Components
- scientific article; zbMATH DE number 3475221 (Why is no real title available?)
- scientific article; zbMATH DE number 3797174 (Why is no real title available?)
- scientific article; zbMATH DE number 3314878 (Why is no real title available?)
- Maximal Flow Through a Network
- Multi-Terminal Network Flows
- A decomposition algorithm for multi-terminal network flows
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Faster network algorithms based on graph decomposition
- Approximate decomposition methods for the analysis of multicommodity flow routing in generalized queuing networks
- scientific article; zbMATH DE number 1004242 (Why is no real title available?)
- scientific article; zbMATH DE number 4156166 (Why is no real title available?)
- A decomposition algorithm for circuit routing
- Sensitivity analysis of 0-1 multiterminal network flows
- A fast algorithm of constructing decomposition of multipole flows
- Simple linear flow decomposition algorithms on trees, circles, and augmented trees
- The decomposition of a communication network considering traffic demand interrelations
- Some LCP decompositions of multistage interconnection networks
This page was built for publication: A decomposition algorithm for multi-terminal network flows
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085042)