^-^
A Correct certificate for the Stoer-Wagner min-cur Algorithm

无向图 且 , 边权 . 定义 表示 weighted adjacency of to .

Stoer-Wagner 算法是这样的: 该算法包含 个阶段, 每一阶段找两个顶点之间的一个 min-cut 然后将它们合并为一个顶点.

的 global min-cut 就是这 个阶段中最小的 cut, 每个阶段的时间为 . 这篇文章给 Stoer-Wagner 算法一个扩展, 每一轮用额外的 的时间再找一个等于 min cut 的 flow.

Stoer-Wagner 用 maximum adjacency search 来给顶点编号, 步骤如下: 1. 随机选一个顶点 标为 , ; 2. For from to , , 然后 标为 并放到 里.

记 是最后编号的两个顶点, 则 是一个 min - cut. 令 , 现在构造一个 to 的值为 的 flow. 现在以编号指代所有顶点, 然后 .

Definition 1 (-Reduction)

2024-10-31 该篇文章被 Baoduo Xu 归为分类: PaperReading

以上
©
Too Young Too Naive 本站由Hexo驱动｜使用Hexo-theme-A4主题