25年来首次实现最小切割算法的运行时改进（2019）
2021-01-11 16:32:32
下载PDF摘要：我们提供了一种随机算法，该算法可以在$ O（m \ log ^ 2 n）$时间内以高概率找到无向加权$ m $-边$ n $-顶点图$ G $中的最小割。这是对1996年Karger著名的$ O（m \ log ^ 3 n）$时间算法的首次改进。我们的主要技术贡献是确定性的$ O（m \ log ^ 3n）$时间算法，该算法具有$ G $的树$ T $，找到了$ G $的最小截距，该截距2尊重（截断了$ T $的两个边）。
从：Oren Weimann [查看电子邮件] [v1] 2019年11月4日星期一11:53:33 UTC（84 KB）[v2] 2019年11月7日星期四08:48:43 UTC（84 KB）[v3] 16月星期一2019年12月10:25:38 UTC（85 KB）[v4] 2020年3月23日星期一06:13:03 UTC（96 KB）[v5] 2020年8月3日星期一09:18:18 UTC（86 KB）
关于arXivLabs arXivLabs是一个允许合作者直接在我们的网站上开发和共享新的arXiv功能的框架。
与arXivLabs合作的个人和组织都已经接受并接受了我们的开放，社区，卓越和用户数据隐私价值。 arXiv致力于这些价值观，并且仅与遵守这些价值观的合作伙伴合作。
有一个可以为arXiv社区增加价值的项目的想法吗？了解有关arXivLabs以及如何参与的更多信息。
书目工具代码推荐
