Halin图上求解最大切割问题的高效算法

摘要

对于一个给定的带权图 G=(V,E),和一个正整数 k ,是否存在一种切割方法,将 V 划分成两个不相交的子集 V 1 和 V 2,使得所有一个端点在 V 1 中,另一个端点在 V 2 中的边的权相加之和大于等于 k ?该问题是在普通图上的一个NPC问题,称为最大切割问题。当各边的权为1时,该问题在普通图上仍是一个NPC问题。提出了一个算法,用于在Halin图上解决最大切割问题,该算法时间复杂度为 O(n),其中 n= V(G)。