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

DOI10.1016/J.TCS.2010.11.019zbMATH Open1230.90045OpenAlexW2000383711MaRDI QIDQ620954FDOQ620954

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

Recommendations

• Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains
• scientific article
• Publication:4726020
• scientific article; zbMATH DE number 934460
• 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

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)

Cites Work

• Title not available (Why is that?)
• Network flows. Theory, algorithms, and applications.
• Title not available (Why is that?)
• Mathematical methods of organizing and planning production. English translation by Robert W. Campbell and W. H. Marlow
• A new polynomial-time algorithm for linear programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Title not available (Why is that?)
• Polynomial algorithms in linear programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Unapproximable Versions of $NP$-Complete Problems
• Combinatorial approximation algorithms for generalized flow problems
• Negative-cycle detection algorithms
• Fast and simple approximation schemes for generalized flow.
• 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
• Title not available (Why is that?)
• A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow
• A polynomial dual simplex algorithm fot the generalized circulation problem.

Cited In (3)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains

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)