Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141463 | Discrete Optimization | 2013 | 12 Pages |
Abstract
The hypergraph k-cut problem is the problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph into at least k connected components. We present an algorithm for this problem, that runs in strongly polynomial time if both k and the maximum size of the hyperedges are constants. Our algorithm extends the algorithm proposed by Thorup (2008) for computing minimum k-cuts of graphs from greedy packings of spanning trees.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Takuro Fukunaga,