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

DOI10.1016/J.TCS.2010.11.019MaRDI QIDQ620954zbMATHOpenAlexFDO

Authors Franz J. Brandenburg, Mao-Cheng Cai

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) Deterministic network models in operations research (90B10) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains
• Publication:3538737
• Publication:4726020
• Publication:4895157
• A SURVEY OF COMBINATORIAL MAXIMUM FLOW ALGORITHMS ON A NETWORK WITH GAINS(<Special Issue>Network Design, Control and Optimization)
• The problem of maximum flow with minimum attainable cost in a network
• Maximum network flows with concave gains
• Algebraic methods applied to shortest path and maximum flow problems in stochastic networks
• The multiroute maximum flow problem revisited
• Randomized shortest paths with net flows and capacity constraints

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1953081 (Why is no real title available?)
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
• A new polynomial-time algorithm for linear programming
• A polynomial dual simplex algorithm fot the generalized circulation problem.
• Combinatorial Algorithms for the Generalized Circulation Problem
• Combinatorial approximation algorithms for generalized flow problems
• Fast and simple approximation schemes for generalized flow.
• Mathematical methods of organizing and planning production. English translation by Robert W. Campbell and W. H. Marlow
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Negative-cycle detection algorithms
• Network flows. Theory, algorithms, and applications.
• New Methods in Mathematical Programming—Optimal Flow Through Networks with Gains
• On Unapproximable Versions of $NP$-Complete Problems
• Polynomial algorithms in linear programming
• Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem

Cited in

(3)

• scientific article; zbMATH DE number 5371757 (Why is no real title available?)
• scientific article; zbMATH DE number 1953081 (Why is no real title available?)
• Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains

Describes a project that uses

Uses Software

• LEDA

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

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