Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract)

Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract)
复制标题

DOI：
10.1007/3-540-55719-9_88
复制
发表时间：
1992-07
期刊：
--
影响因子：
--
通讯作者：
V. Vazirani;M. Yannakakis
V. Vazirani;M. Yannakakis
中科院分区：
其他
文献类型：
--
作者：
V. Vazirani;M. Yannakakis

文献摘要

被引文献

相似文献

我们提出了（1）一个通过增加多项式延迟的权值来枚举网络割集的算法，以及（2）一个在多项式时间内计算k个最小权值的算法。我们还证明了在无向网络的情况下，对于任意的k个最小权值，只有多项式数量的割集具有k个最小权值（而有向网络可以有指数数量的不同的最小割集）。
We present (1) an algorithm that enumerates the cuts of a network by increasing weight with polynomial delay, and (2) an algorithm that computes thek-th minimum weight in polynomial time for fixedkWe also show that in the case of undirected networks there are only polynomially many cuts that have thek-th minimum weight for any fixedk(whereas directed networks can have exponentially many different minimum cuts).