Multi-terminal maximum flows in node-capacitated networks

DOI10.1016/0166-218X(86)90079-XMaRDI QIDQ1085773zbMATH OpenOpenAlexFDO

Authors Frieda Granot, Refael Hassin

Publication date 1986

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(86)90079-x

zbMATH Keywords

communication and transportation networksgeneral node- and arc-capacited casemulti-terminal maximum flowsundirected network

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Deterministic network models in operations research (90B10)

Review text

The problem of finding the maximum flows between each pair of nodes in a subset of K nodes of a node- and arc-capacitated undirected network is considered. This problem arises in the study of communication and transportation networks. \textit{R. E. Gomory} and \textit{T. C. Hu} [SIAM J. Appl. Math. 9, 551-570 (1961; Zbl 0112.124)] solved the arc-capacited case for this problem. The purpose of this paper is to extend Gomory and Hu's result to the general node- and arc-capacited case.

Recommendations

• Min-cost multiflows in node-capacitated undirected networks
• On multiroute maximum flows in networks.
• scientific article; zbMATH DE number 4053314
• An Algorithm for the Maximal Multicommodity Funnel-Node Flow in an Undirected Network
• Generalized parametric multi-terminal flows problem.

Cites work

• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• scientific article; zbMATH DE number 3475221 (Why is no real title available?)
• Multi-Terminal Network Flows
• On the shortest spanning subtree of a graph and the traveling salesman problem

Cited in

(25)

• Multiterminal xcut problems
• Maximum concurrent flows and minimum cuts
• Extracting maximal information about sets of minimum cuts
• A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
• Flow in planar graphs with vertex capacities
• Generalizing the all-pairs min cut problem
• Min-cost multiflows in node-capacitated undirected networks
• Optimal flow and capacity allocation in multiple joint quickest paths of directed networks
• Optimum synthesis of discrete capacitated networks with multi-terminal commodity flow requirements
• An algorithm for computing maximum solution bases
• The maximum integer multiterminal flow problem in directed graphs
• On multiroute maximum flows in networks.
• Designing FPT algorithms for cut problems using randomized contractions
• The Maximum Integer Multiterminal Flow Problem
• An Algorithm for the Maximal Multicommodity Funnel-Node Flow in an Undirected Network
• An algorithm for finding all thek-components of a digraph
• The optimal partitioning of networks
• scientific article; zbMATH DE number 754202 (Why is no real title available?)
• New algorithms and lower bounds for all-pairs max-flow in undirected graphs
• The multiroute maximum flow problem revisited
• An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems
• Vital edges for (s,t)-mincut: efficient algorithms, compact structures, \& optimal sensitivity oracles
• The structure of minimum vertex cuts
• A maximum flow problem with intermediate node requirements
• Flow trees for vertex-capacitated networks

This page was built for publication: Multi-terminal maximum flows in node-capacitated networks

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