On budget-constrained flow improvement.

DOI10.1016/S0020-0190(98)00070-2MaRDI QIDQ2583570zbMATH OpenOpenAlexFDO

Authors S. Schwarz, Sven O. Krumke

Publication date 17 January 2006

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(98)00070-2

zbMATH Keywords

AlgorithmsNP-completenessComplexityMaximum flowMinimum cost flow

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1859293
• On the complexity and approximability of budget-constrained minimum cost flows
• Optimizing cost flows by edge cost and capacity upgrade
• scientific article; zbMATH DE number 1696527
• On the flow cost lowering problem

Cites work

• scientific article; zbMATH DE number 1263260 (Why is no real title available?)
• scientific article; zbMATH DE number 871953 (Why is no real title available?)
• An efficient approximation algorithm for the survivable network design problem
• Analysis of a flow problem with fixed charges
• Approximation Schemes for the Restricted Shortest Path Problem
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Augmenting Undirected Edge Connectivity in Õ(n2) Time
• Edge Weight Reduction Problems in Directed Acyclic Graphs
• Improving Minimum Cost Spanning Trees by Upgrading Nodes
• Linear-time computation of optimal subgraphs of decomposable graphs
• Minimum concave-cost network flow problems: Applications, complexity, and algorithms
• Modifying edges of a network to obtain short subgraphs
• Network flows. Theory, algorithms, and applications.
• Network upgrading problems
• The Recognition of Series Parallel Digraphs
• Two-Processor Scheduling with Start-Times and Deadlines

Cited in

(15)

• Further study on reverse 1-center problem on trees
• Budget-constrained minimum cost flows
• A network simplex method for the budget-constrained minimum cost flow problem
• Optimizing cost flows by edge cost and capacity upgrade
• scientific article; zbMATH DE number 1859293 (Why is no real title available?)
• On the complexity and approximability of budget-constrained minimum cost flows
• Improving spanning trees by upgrading nodes
• Some budget applications of the maximal flow
• Interdiction problems on planar graphs
• Approximation Algorithms for k-Hurdle Problems
• Approximation algorithms for \(k\)-hurdle problems
• Robust flows with losses and improvability in evacuation planning
• Resource allocation by means of project networks: dominance results
• On the optimum capacity of capacity expansion problems
• On the budget exercise problem

This page was built for publication: On budget-constrained flow improvement.

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