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

摘要

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