Abstract:
Given an undirected, unweighted graph with n vertices and m edges, the maximum cut problem is to find a partition of the n vertices into disjoint subsets V1 and V2 such that the number of edges between them is as large as possible. Classically, it is an NP-complete problem, which …