Between Min Cut and Graph Bisection
Between Min Cut and Graph Bisection
复制标题
DOI：
10.1007/3-540-57182-5_65
复制
发表时间：
1993-08
期刊：
影响因子：
--
通讯作者：
D. Wagner;Frank Wagner
中科院分区：
文献类型：
--
作者：
D. Wagner;Frank Wagner
我们研究了一类图划分问题，其两个极端的代表是著名的最小割和图二分问题。前者被认为是有效的解决流动技术，后者是NP完全的。本文给出的结果是”我们所寻求的划分越平衡，问题就越难”的单调性结果，是一个复杂性结果，澄清了类中大部分中间问题的地位，从而证明了两个极端之间的”效率边界”的存在性，并部分地局部化了它.
We investigate a class of graph partitioning problems whose two extreme representatives are the well-known Min Cut and Graph Bisection problems. The former is known to be efficiently solvable by flow techniques, the latter to beNP-complete. The results presented in this paper area monotony result of the type“ The more balanced the partition we look for has to be, the harder the problem”.a complexity result clarifying the status of a large part of intermediate problems in the class.Thus we show the existence and partly localize an“ efficiency border” between the two extremes.