| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427590 | Information Processing Letters | 2010 | 5 Pages |
Abstract
The minimum 3-way cut problem in an edge-weighted hypergraph is to find a partition of the vertices into 3 nonempty sets minimizing the total weight of hyperedges that have at least two endpoints in two different sets. In this paper we show that a minimum 3-way cut in hypergraphs can be found by using O(n3) hypergraph minimum (s,t) cut computations, where n is the number of vertices in the hypergraph. Our simple algorithm is the first polynomial-time algorithm for finding minimum 3-way cuts in hypergraphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
