Fast algorithms for convex cost flow problems on circles, lines, and trees

DOI10.1002/net.21517zbMath1338.05109OpenAlexW2012406502WikidataQ59592270 ScholiaQ59592270MaRDI QIDQ2811315

James B. Orlin, Balachandran Vaidyanathan

Publication date: 10 June 2016

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.21517

zbMATH Keywords

computational complexityapplicationsminimum cost flowsnetwork flow algorithmsconvex cost flows

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21)

Related Items (2)

Simple linear flow decomposition algorithms on trees, circles, and augmented trees ⋮ On a Reduction for a Class of Resource Allocation Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Two special cases of the assignment problem
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• Time bounds for selection
• A data structure for dynamic trees
• Dynamic Version of the Economic Lot Size Model
• Fast Algorithms for Specially Structured Minimum Cost Flow Problems with Applications
• Capacity Acquisition, Subcontracting, and Lot Sizing
• TECHNICAL NOTE—Solving Linear Cost Dynamic Lot-Sizing Problems in O(n log n) Time
• Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case
• Efficiency of a Good But Not Linear Set Union Algorithm
• Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• Simple linear flow decomposition algorithms on trees, circles, and augmented trees

This page was built for publication: Fast algorithms for convex cost flow problems on circles, lines, and trees