Minimum multiway cuts in trees

✍ Scribed by Péter L. Erdős; András Frank; László Székely

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 667 KB
• Volume: 87
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(98)00049-3

✦ Synopsis

We compare three lower bounds for the minimum cardinality of a multiway cut in a graph separating a given set S of terminals. The main result is a relatively short algorithmic proof for a simplified version of a min-max theorem of the first and the third authors asserting that the best of the three lower bounds is actually attainable if every circuit of the graph contains a terminal node.