Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains

DOI10.1007/978-3-642-02270-8_4zbMath1248.68211OpenAlexW2140265247MaRDI QIDQ5321689

Mao-cheng Cai, Franz-Josef Brandenburg

Publication date: 14 July 2009

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02270-8_4

zbMATH Keywords

shortest pathNP-hardmax-flowextended networkslossy and gainy arcsunit-loss networks

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) 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
• 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-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