On budget-constrained flow improvement.

DOI10.1016/S0020-0190(98)00070-2zbMath1078.68641MaRDI QIDQ2583570

Sven O. Krumke, S. Schwarz

Publication date: 17 January 2006

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

zbMATH Keywords

Algorithms; Complexity; Minimum cost flow; NP-completeness; Maximum flow

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

Related Items

Approximation Algorithms for k-Hurdle Problems, Budget-constrained minimum cost flows, Robust flows with losses and improvability in evacuation planning, Approximation algorithms for \(k\)-hurdle problems, Interdiction problems on planar graphs, A network simplex method for the budget-constrained minimum cost flow problem, Improving spanning trees by upgrading nodes, On the optimum capacity of capacity expansion problems, Resource allocation by means of project networks: Dominance results

Cites Work

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