Multicommodity flows in certain planar directed networks

DOI10.1016/0166-218X(90)90134-XzbMath0716.90033MaRDI QIDQ753654

Hiroshi Nagamochi, Toshihide Ibaraki

Publication date: 1990

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

zbMATH Keywords

multicommodity flowsfeasibility testdirected networkscapacity balancedmulti-item multi- stage production schedulingpolynomial time graph theoretic algorithm

Mathematics Subject Classification ID

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

Related Items

Relaxation methods for the strictly convex multicommodity flow problem with capacity constraints on individual commodities, Disjoint paths in symmetric digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dual version of Tardos's algorithm for linear programming
• A new polynomial-time algorithm for linear programming
• Multicommodity flows in planar graphs
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• A Survey of Linear Cost Multicommodity Network Flows
• Multi-Commodity Network Flows