Shortest path and maximum flow problems in networks with additive losses and gains

DOI10.1016/j.tcs.2010.11.019zbMath1230.90045OpenAlexW2000383711MaRDI QIDQ620954

Mao-cheng Cai, Franz-Josef Brandenburg

Publication date: 2 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.11.019

zbMATH Keywords

NP-hard problemsshortest path problemsextended networkslossy and gainy arcsmax-flow problemsunit-loss networks

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Negative-cycle detection algorithms
• Combinatorial Approximation Algorithms for Generalized Flow Problems
• Mathematical Methods of Organizing and Planning Production
• Combinatorial Algorithms for the Generalized Circulation Problem
• New Methods in Mathematical Programming—Optimal Flow Through Networks with Gains
• Polynomial algorithms in linear programming
• Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem
• On Unapproximable Versions of $NP$-Complete Problems
• A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
• Fast and simple approximation schemes for generalized flow.
• A polynomial dual simplex algorithm fot the generalized circulation problem.

This page was built for publication: Shortest path and maximum flow problems in networks with additive losses and gains