On greedy algorithms for series parallel graphs
type: Item
instance of: scholarly article
title: On greedy algorithms for series parallel graphs
zbMATH Open document ID: 0652.90040
DOI: 10.1007/BF01580730
author: Alan J. Hoffman
published in: Mathematical Programming. Series A. Series B
publication date: 1988-01-01T00:00:00Z
review text: Let G be a directed multigraph with single source s and sink t, \({\mathcal P}\) the set of all s-t (directed) paths, b: E(G)\(\to {\mathbb{R}}_+\) an (edge-)capacity function and c: \({\mathcal P}\to {\mathbb{R}}\) arbitrary path- costs. The problems, the author is concerned with, are \[ \bar P(v):\quad \max \quad \sum_{P\in {\mathcal P}}c(P)x(P) \] subject to (1.1) x(P)\(\geq 0\) for all \(P\in {\mathcal P}\), (1.2) \(\sum_{e\in P}x(P)\leq b(e)\) for all \(e\in E(G)\), (1.3) \(\sum_{P\in {\mathcal P}}x(P)=v\), and respectively, \b{P}(v): minimize the objective function under (1.1)-(1.3). The author proves that \(\bar P(v)\) and \b{P}(v) can be optimally solved by a greedy algorithm, if G is a series parallel graph, c is obtained by the (edge-)values b(e) in the following way: \(c(P)=\sum_{e\in P}b(e)\) and c obeys some simple algebraic (associative, monotonic) and lattice- theoretic properties.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 4064734
zbMATH Keywords: flows in networks
zbMATH Keywords: single sink
zbMATH Keywords: directed multigraph
zbMATH Keywords: single source
zbMATH Keywords: greedy algorithm
zbMATH Keywords: series parallel graph
reviewed by: Hartmut Noltemeier
MaRDI profile type: Publication
cites work: Classes of linear programs with integral optimal solutions
cites work: Minimum cost flow algorithms for series-parallel networks
description: scientific article; zbMATH DE number 4064734