On greedy algorithms for series parallel graphs (Q1107418)

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.