Computing All Small Cuts in an Undirected Network
Computing All Small Cuts in an Undirected Network
复制标题
计算无向网络中的所有小切口
DOI：
10.1137/s0895480194271323
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
T. Ibaraki
中科院分区：
文献类型：
--
作者：
H. Nagamochi;Kazuhiro Nishimura;T. Ibaraki
令$ \ lambda（{\ cal n}）$表示在边缘加权的无向网络$ {\ cal n} $中的最小切割的重量分别。众所周知，$ o（n^{2k}）$是重量小于$ k \ lambda（{\ cal n}）$的削减次数的上限，其中$ k \ geq 1 $是给定的持续的。本文首先表明，所有小于$ k \ lambda（{\ cal n}）$的权重可以在$ o（m^2n+n^{2k} m）$ time中枚举，而无需使用最大流量算法。然后，该论文以$ k <\ 4 $的证明，$ n \选择2 $是小于$ k \ lambda（{\ cal n}）$的削减数量的紧密上限，并且所有这些切割可以在$ o（m^2n+Mn^2 \ log n）$时间中枚举。
Let $\lambda({\cal N})$ denote the weight of a minimum cut in an edge-weighted undirected network ${\cal N}$, and $n$ and $m$ denote the numbers of vertices and edges, respectively. It is known that $O(n^{2k})$ is an upper bound on the number of cuts with weights less than $k\lambda({\cal N})$, where $k\geq 1$ is a given constant. This paper first shows that all cuts of weights less than $k\lambda({\cal N})$ can be enumerated in $O(m^2n+n^{2k}m)$ time without using the maximum flow algorithm. The paper then proves for $k<\four$ that $n\choose 2$ is a tight upper bound on the number of cuts of weights less than $k\lambda({\cal N})$, and that all those cuts can be enumerated in $O(m^2n+mn^2\log n)$ time.