A Greedy Algorithm for Solving Network Flow Problems in Trees

Abstract

Let (H,*,⩽) be a d-monoid and T an intree with root r. For each vertex j let L(j) be the set of leaves of the subtree rooted in j. Associated with the leaves of T are monotone functions from Z+ into H satisfying some type of convexity properties. A Greedy algorithm is given which solves the following integer algebraic network flow problem: Minimize for all j∈T. © 1984, Elsevier Science & Technology. All rights reserved.