Minimum cost flow algorithms for series-parallel networks

DOI10.1016/0166-218X(85)90006-XzbMath0571.90019OpenAlexW2009550509MaRDI QIDQ1061597

Peter Brucker, Wolfgang W. Bein, Arie Tamir

Publication date: 1985

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(85)90006-x

zbMATH Keywords

greedy algorithmminimum cost flow problemacyclic multigraphseries parallelsingle sinksingle source

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Related Items (26)

Budget-constrained minimum cost flows ⋮ A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks ⋮ Greedy concepts for network flow problems ⋮ Computation of equilibria and the price of anarchy in bottleneck congestion games ⋮ On greedy algorithms for series parallel graphs ⋮ Greedy packing and series-parallel graphs ⋮ Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs ⋮ Perspectives of Monge properties in optimization ⋮ Robust minimum cost flow problem under consistent flow constraints ⋮ Inefficiencies in network models: a graph-theoretic perspective ⋮ Minimum cost dynamic flows: The series-parallel case ⋮ Integrality in the multinetwork min‐cost equal‐flow problem ⋮ Series-parallel orientations preserving the cycle-radius ⋮ Measuring the distance to series-parallelity by path expressions ⋮ Unnamed Item ⋮ Generalized max flow in series-parallel graphs ⋮ The inverse 1-maxian problem with edge length modification ⋮ A note on integral generalized flows in directed partial 2-trees ⋮ Maximum flows in generalized processing networks ⋮ Stackelberg strategies for atomic congestion games ⋮ The edge versus path incidence matrix of series-parallel graphs and greedy packing ⋮ Earliest arrival flows on series-parallel graphs ⋮ How hard is it to find extreme Nash equilibria in network congestion games? ⋮ The nestedness property of the convex ordered median location problem on a tree ⋮ Some recent results in the analysis of greedy algorithms for assignment problems ⋮ Series parallel composition of greedy linear programming problem

Cites Work

• Efficient Algorithms for a Selection Problem with Nested Constraints and Its Application to a Production-Sales Planning Model
• The Recognition of Series Parallel Digraphs
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimum cost flow algorithms for series-parallel networks