Publikationsansicht

The complexity of multiterminal cuts (1994)

Abstract

In the Multiterminal Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and 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. We show 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. We also describe a simple approximation algorithm for arbitrary graphs that is guaranteed to come within a factor of 2- 2/k of the optimal cut weight.

Details der Publikation

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=?doi=10.1.1.13.6534
Quelle	http://www.research.att.com/~dsj/papers/3way.ps
Mitarbeiter	CiteSeerX
Archiv	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Typ	text
Sprache	Englisch
Verknüpfungen	10.1.1.22.8587, 10.1.1.91.1599, 10.1.1.51.3217, 10.1.1.32.1401, 10.1.1.31.3602, 10.1.1.115.4317, 10.1.1.132.2721, 10.1.1.104.2928, 10.1.1.100.8049, 10.1.1.30.9776, 10.1.1.100.6715, 10.1.1.39.1508, 10.1.1.6.4311, 10.1.1.1.2455, 10.1.1.96.981, 10.1.1.102.9011, 10.1.1.97.7048, 10.1.1.105.1361, 10.1.1.32.8213, 10.1.1.46.2150, 10.1.1.120.768, 10.1.1.24.9686, 10.1.1.36.8514, 10.1.1.106.3147, 10.1.1.37.3108, 10.1.1.78.461, 10.1.1.84.2489, 10.1.1.125.5644, 10.1.1.135.5760, 10.1.1.61.1959, 10.1.1.111.1781, 10.1.1.104.2170, 10.1.1.22.2311, 10.1.1.63.553, 10.1.1.63.6476, 10.1.1.72.8925, 10.1.1.87.629, 10.1.1.120.6790, 10.1.1.129.8697, 10.1.1.131.3898, 10.1.1.105.4485, 10.1.1.105.9472, 10.1.1.107.6137, 10.1.1.108.3210, 10.1.1.108.3711, 10.1.1.108.8028, 10.1.1.21.6802, 10.1.1.22.2899, 10.1.1.22.8321, 10.1.1.23.9726, 10.1.1.24.875, 10.1.1.27.2960, 10.1.1.31.7483, 10.1.1.31.9693, 10.1.1.36.2070, 10.1.1.37.3615, 10.1.1.38.1680, 10.1.1.39.5603, 10.1.1.4.6912, 10.1.1.44.4773, 10.1.1.46.1754, 10.1.1.46.3128, 10.1.1.6.9216, 10.1.1.61.7191, 10.1.1.68.4227, 10.1.1.68.8780, 10.1.1.69.4024, 10.1.1.70.1471, 10.1.1.112.2718, 10.1.1.74.4071, 10.1.1.8.9964, 10.1.1.80.1601, 10.1.1.86.578, 10.1.1.87.7602, 10.1.1.92.8224, 10.1.1.95.663, 10.1.1.95.9935, 10.1.1.96.9257, 10.1.1.97.1940, 10.1.1.98.3223, 10.1.1.110.731, 10.1.1.111.4120, 10.1.1.119.5256, 10.1.1.120.3993, 10.1.1.120.9544, 10.1.1.121.4165, 10.1.1.121.8811, 10.1.1.125.2557, 10.1.1.126.99, 10.1.1.122.7397, 10.1.1.134.9195, 10.1.1.136.2515