On budget-constrained flow improvement.

DOI10.1016/S0020-0190(98)00070-2zbMATH Open1078.68641OpenAlexW1983839752MaRDI QIDQ2583570FDOQ2583570

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

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

zbMATH Keywords

AlgorithmsNP-completenessComplexityMaximum flowMinimum cost flow

Mathematics Subject Classification ID

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

Cites Work

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

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
• Title not available (Why is that?)
• 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)