我知道在平面图中找到最小切割的算法。
工作为 O(NlogN)
您创建一个对偶图，其中每个顶点对应于原始图形的分面，边对应于连接两个分面的最小边。
然后您使用 Dijkstra 在此图中找到最小路径。
通过这种方式，可以找到最小切割并计算流量值。
但是我怎样才能找到提供这个流量值的任何一组原始图边呢？
问问题
1449 次
1 回答
3
您描述的算法仅适用于无向图（Reif 算法）。Hassin 和 Johnson 展示了如何通过它来计算最大流量。最近表明，这些算法可以在 O(n loglog n) 时间内实现。请参阅 GF Italiano、Y. Nussbaum、P. Sankowski 和 C. Wulff-Nilsen 改进无向平面图中最小切割和最大流量的算法。在过程中。第 43 届 ACM 计算理论研讨会 (STOC)，圣何塞，2011 年。
在有向平面图中，已知最快的算法在 O(n log n) 中运行，请参阅 http://web.engr.oregonstate.edu/~glencora/papers/other/Borradaile08-thesis-dissertation.pdf或 http://compgeom。 cs.uiuc.edu/~jeffe/pubs/parshort.html
于 2012-05-19T19:44:14.513 回答