一般图上的推广的最小k——cut问题的求解算法

原始割集问题是图论几大经典问题之一,在实际中应用广泛。割集问题有很多较为复杂的推广问题,如最小multicut问题和最小multiwaycut问题等。本文主要讨论的是割集问题的另一推广问题最小k--cut问题,并且给出了一个时间复杂度为O(mlog2m)的近似算法求得该问题的可行解。