摘要
我们展示了寻找任意权重平面图的最大割问题可以轻松映射到绝对对偶图中的最小 T-连接问题，而不是已知的映射到对偶图中空集的最大 T-连接问题。通过利用最短路径，该方法使得 Hadlock 在 1975 年为非负权重平面图设计的第一个高效最大割算法可以轻松适应处理任意权重的平面图。
此外，我们证明了将平面最大割算法应用于更高 genus 的图（如环面图）时，忽略其拓扑结构可以为其最大割提供上界。采用这种方法，我们推导出 GSet 基准中所有环面图的最大割的上界。
我们报告说，已知的最大割值对于部分 GSet 环面问题，包括三个最大的实例，因其与上界值相符而成为最大可能值。此外，我们基于平面图算法引入了一种新颖的启发式算法，用于寻找环面图的最大割。将该算法应用于 GSet 基准中所有十七个环面最大割问题，成功重现了所有已知最佳结果，并且对于问题 #62，得出了一个新的、先前未知的最佳最大割值。
博主点评： 该研究巧妙地将平面图的最大割问题与绝对对偶图的最小 T-连接问题相联系，为处理任意权重图提供了新的视角。尤其是其对环面图的探索，显示了拓扑结构在最大割计算中的重要性，值得进一步研究与实践应用。