Minimum cost flow algorithms for series-parallel networks
type: Item
instance of: scholarly article
title: Minimum cost flow algorithms for series-parallel networks
zbMATH Open document ID: 0571.90019
DOI: 10.1016/0166-218X(85)90006-X
author: Wolfgang W. Bein
author: Peter Brucker
author: Arie Tamir
published in: Discrete Applied Mathematics
publication date: 1985-01-01T00:00:00Z
review text: It is shown that an acyclic multigraph with a single source and a single sink is series parallel if and only if for arbitrary linear cost functions and arbitrary capacities the corresponding minimum cost flow problem can be solved by a greedy algorithm. Furthermore, for networks of this type with m edges and n vertices, two \(O(mn+m \log m)\)-algorithms are presented. One of them is based on the greedy scheme.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3912064
zbMATH Keywords: acyclic multigraph
zbMATH Keywords: single source
zbMATH Keywords: single sink
zbMATH Keywords: series parallel
zbMATH Keywords: minimum cost flow problem
zbMATH Keywords: greedy algorithm
MaRDI profile type: Publication
cites work: Q3318501
cites work: Q3332729
cites work: Efficient Algorithms for a Selection Problem with Nested Constraints and Its Application to a Production-Sales Planning Model
cites work: The Recognition of Series Parallel Digraphs
full work available at URL: 0166-218x(85)90006-x
OpenAlex ID: W2009550509
description: scientific article; zbMATH DE number 3912064