Name
Abstract | ||
|---|---|---|
In the multiterminal cut problem one is given an edge-weighted graph and a subset of the vertices called terminals, and is asked for a minimum weight set of edges that separates each terminal from all the others. When the number $k$ of terminals is two, this is simply the mincut, max-flow problem, and can be solved in polynomial time. It is shown that the problem becomes NP-hard as soon as $k=3$, but can be solved in polynomial time for planar graphs for any fixed $k$. The planar problem is NP-hard, however, if $k$ is not fixed. A simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of $2-2/k$ of the optimal cut weight is also described. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1137/S0097539792225297 | SIAM J. Comput. |
Keywords | Field | DocType |
simple approximation algorithm,edge-weighted graph,planar problem,max-flow problem,multiterminal cuts,planar graph,minimum weight,multiterminal cut problem,polynomial time,arbitrary graph,optimal cut weight,network flow,np completeness,planar graphs | Flow network,Discrete mathematics,Approximation algorithm,Combinatorics,Vertex (geometry),Planar,Minimum weight,Time complexity,Mathematics,Planar graph,Computational complexity theory | Journal |
Volume | Issue | ISSN |
23 | 4 | 0097-5397 |
Citations | PageRank | References |
235 | 20.53 | 15 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| E. Dahlhaus | 1 | 303 | 47.68 |
| Dayid S. Johnson | 2 | 2213 | 870.42 |
| Christos H. Papadimitriou | 3 | 16671 | 3192.54 |
| P. D. Seymour | 4 | 297 | 32.84 |
| Mihalis Yannakakis | 5 | 11141 | 2069.50 |