重み付けされていない無向グラフ上のグローバルな最小カット数を数えるという決定論的な複雑さは何ですか?

Kargerのアルゴリズムの結果、最小カットの数は$ binom {n} {2}
$で制限されていることが分かります。のコメント


別個のstの数を数える方向付けされたグラフでカットする

このようにして、重み付けされていないグラフのカットを多項式時間でリストすることができますが、クレームは参照されません。

ベストアンサー

If you want exact minimum cuts then one can construct a cactus
representation of the minimum cuts deterministically in polynomial
time and use that to enumerate all minimum cuts. See below for a
reference. https://www.sciencedirect.com/science/article/pii/S0196677499910398

More interesting and difficult case is $alpha$-approximation
mincuts for $alpha > 1$. One can use Karger’s randomized
algorithm for this purpose. Simply run it sufficiently many time.
However, if you want a deterministic algorithm, one can do it via
tree packings. See Thorup’s paper on k-cuts. https://dl.acm.org/citation.cfm?id=365415

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です