Greedy concepts for network flow problems

DOI10.1016/0166-218X(86)90037-5MaRDI QIDQ1088884zbMATH OpenFDO

Authors Wolfgang W. Bein, Peter Brucker

Publication date 1986

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

Full work available at URL https://doi.org/10.1016/0166-218X(86)90037-5

zbMATH Keywords

augmenting path methodcost optimal flowgreedy algorithmparallel compositionpolymatroidalseries compositionseries-parallel networkstree structures

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Deterministic network models in operations research (90B10)

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.

Recommendations

• Minimum cost flow algorithms for series-parallel networks
• On greedy algorithms for series parallel graphs
• Finding the Minimum-Cost Maximum Flow in a Series-Parallel Network
• scientific article; zbMATH DE number 1029233
• Series parallel composition of greedy linear programming problem

Cites work

• scientific article; zbMATH DE number 3848941 (Why is no real title available?)
• scientific article; zbMATH DE number 3864952 (Why is no real title available?)
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 3970528 (Why is no real title available?)
• Minimum cost flow algorithms for series-parallel networks
• On Transportation Problems with Upper Bounds on Leading Rectangles
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• The Recognition of Series Parallel Digraphs

Cited in

(10)

• Minimum cost flow algorithms for series-parallel networks
• On greedy algorithms for series parallel graphs
• Greedy packing and series-parallel graphs
• Some recent results in the analysis of greedy algorithms for assignment problems
• Series parallel composition of greedy linear programming problem
• Greedy oriented flows
• Generating two-terminal directed acyclic graphs with a given complexity index by constraint logic programming
• scientific article; zbMATH DE number 3904297 (Why is no real title available?)
• scientific article; zbMATH DE number 1029233 (Why is no real title available?)
• scientific article; zbMATH DE number 2079418 (Why is no real title available?)

This page was built for publication: Greedy concepts for network flow problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1088884)