Multicommodity flows in certain planar directed networks

DOI10.1016/0166-218X(90)90134-XMaRDI QIDQ753654zbMATH OpenFDO

Authors Hiroshi Nagamochi, Toshihide Ibaraki

Publication date 1990

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

zbMATH Keywords

directed networksfeasibility testmulticommodity flowscapacity balancedmulti-item multi- stage production schedulingpolynomial time graph theoretic algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• On max-flow min-cut and integral flow properties for multicommodity flows in directed networks
• On multicommodity flows in planar graphs
• Algorithms for multicommodity flows in planar graphs
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3791941 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A Survey of Linear Cost Multicommodity Network Flows
• A dual version of Tardos's algorithm for linear programming
• A new polynomial-time algorithm for linear programming
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Multi-Commodity Network Flows
• Multicommodity flows in planar graphs

Cited in

(6)

• Multicommodity Flows in Ring Networks
• On max-flow min-cut and integral flow properties for multicommodity flows in directed networks
• Relaxation methods for the strictly convex multicommodity flow problem with capacity constraints on individual commodities
• Disjoint paths in symmetric digraphs
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• Multicommodity flows in cycle graphs

This page was built for publication: Multicommodity flows in certain planar directed networks

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