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)

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)