Two-Commodity Flow

DOI10.1145/322092.322100zbMATH Open0388.68054OpenAlexW2052768371MaRDI QIDQ4170247FDOQ4170247

Authors: Alon Itai 

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322092.322100

Mathematics Subject Classification ID

Linear programming (90C05) Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Paths and cycles (05C38) Algorithms in computer science (68W99)

Cited In (27)

• Partitioning trees: Matching, domination, and maximum diameter
• An exponential (matching based) neighborhood for the vehicle routing problem
• The complexity of bottleneck labeled graph problems
• A new strategy for the undirected two-commodity maximum flow problem
• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• On Nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles.
• Bottleneck subset-type restricted matching problems
• Max-balanced flows in oriented matroids
• The Maximum Flow Problem for Oriented Flows
• Computing the throughput of a network with dedicated lines
• Synthesis of directed multicommodity flow networks
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• The complexity of linear programming
• Combinatorial analysis (nonnegative matrices, algorithmic problems)
• Simple and improved parameterized algorithms for multiterminal cuts
• Performing Multicut on Walkable Environments
• Algorithms and complexity analysis for some flow problems
• NP-Complete operations research problems and approximation algorithms
• The biobjective undirected two-commodity minimum cost flow problem
• Problems hard for treewidth but easy for stable gonality
• A Representation of bipartite graphs by digraphs and its programming application
• A constrained matching problem
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Quadratic vertex kernel for rainbow matching
• Multicommodity flows in tree-like networks
• On unicyclic graphs with uniquely restricted maximum matchings
• Hardness results for structured linear systems

This page was built for publication: Two-Commodity Flow

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