Crossing properties of multiterminal cuts

✍ Scribed by Easley, Robert F.; Hartvigsen, David

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 80 KB
• Volume: 34
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199910)34:3<215::aid-net6>3.0.co;2-e

✦ Synopsis

Gomory and Hu proved the following classical result: For any graph with nonnegative edge weights, there exists a collection of noncrossing cuts that contains a minimum cut for every pair of nodes. In this paper, we show how this result generalizes for a natural multiterminal cut problem. We also show that our result is "best possible," for k ϭ 3, by using a computer to find feasible solutions to several large systems of linear inequalities.