Algorithms for graph partitioning on the planted partition model
Algorithms for graph partitioning on the planted partition model
复制标题
DOI：
10.1002/1098-2418(200103)18:2
复制
发表时间：
1999-08
期刊：
影响因子：
--
通讯作者：
A. Condon;R. Karp
中科院分区：
文献类型：
--
作者：
A. Condon;R. Karp
NP-hard图的二分问题是将无向图的节点划分为两个大小相等的组，使得穿过划分的边数最少。更一般的图l-划分问题是将无向图的节点划分为l个大小相等的组，以最小化组之间交叉的边的总数。
The NP-hard graph bisection problem is to partition the nodes of an undirected graph into two equal-sized groups so as to minimize the number of edges that cross the partition. The more general graph l-partition problem is to partition the nodes of an undirected graph into l equal-sized groups so as to minimize the total number of edges that cross between groups.