Greedy concepts for network flow problems
type: Item
instance of: scholarly article
title: Greedy concepts for network flow problems
zbMATH Open document ID: 0617.90027
DOI: 10.1016/0166-218X(86)90037-5
author: Wolfgang W. Bein
author: Peter Brucker
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: The problem of finding a cost optimal flow in series-parallel networks can be solved by the greedy algorithm which in this case is identical to the augmenting path method. In this paper the same result is derived by demonstrating that series composition and parallel composition preserves the property that the problem can be solved by the greedy algorithm. This leads to an algorithm which is different from the augmenting path method. Applications of these concepts to tree structures are discussed and it is shown that these structures are polymatroidal in contrast to the series- parallel case.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4001834
zbMATH Keywords: cost optimal flow
zbMATH Keywords: series-parallel networks
zbMATH Keywords: greedy algorithm
zbMATH Keywords: augmenting path method
zbMATH Keywords: series composition
zbMATH Keywords: parallel composition
zbMATH Keywords: tree structures
zbMATH Keywords: polymatroidal
reviewed by: Eleonor Ciurea
MaRDI profile type: Publication
cites work: On Transportation Problems with Upper Bounds on Leading Rectangles
cites work: Minimum cost flow algorithms for series-parallel networks
cites work: Q3318501
cites work: Q3332729
cites work: Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
cites work: Q3737235
cites work: Q3682236
cites work: The Recognition of Series Parallel Digraphs
description: scientific article; zbMATH DE number 4001834