MINIMUM MULTIWAY CUTS IN TREES

We compare three lower bounds for the minimum cardinality of a multiwa y cut in a graph separating a given set S of terminals. The main resul t is a relatively short algorithmic proof for a simplified version of a min-max theorem of the first and the third authors asserting that th e best of the three lower bounds is actually attainable if every circu it of the graph contains a terminal node. (C) 1998 Elsevier Science B. V. All rights reserved.