lim*_*nic 7 graph-theory graph
前段时间我读到了一般的mininum cut算法,该算法将图形作为输入并删除min.边数,使两个断开的组件保留.
我现在正在研究一个带有10k +节点和500k +边缘的无向图(两个顶点之间没有多个边).为了定义节点之间的交互,我考虑计算断开两个给定顶点(或与流量相关的度量)的最小切割.
是否有有效的算法为图中的每对顶点提出一个值(最小割集的基数)？如果有人能提供链接到论文或其他资源的链接,概述在合理的运行时复杂性下运行的算法,我将非常感激.
谢谢!
有几种算法(参见Wiki的介绍)可以找到网络中的最大流量.那些我认识的人(Ford-Fulkerson,Dinic,Karp-Edmond)应该在单位容量方面表现良好(= 所有边缘的整数容量等于1)(可变容量会增加复杂性并且非整数容量会出现更多问题)
对于任何一对顶点,您可以通过将source/sink设置为此对来从图形创建网络.您可以使用其中一种算法获得最大流量,您可以使用这些算法进行如下切割:
最后,您有最小切割,最大流量的大小.
如果你真的想要表现,你可能想看一下这篇论文:Andrew V. Goldberg,Satish Rao 在无向单位容量网络(1997)中的流动,但我可能会坚持使用更简单的那些.