Abstract
The original minimax/maximin cut problem is to find a cutset to minimize/maximize the maximal/minimal weight edge in this cutset. In this paper, we first introduce a stronger definition of the minimax/maximin cut problem such that the total weight in the minimax/maximin cut is also minimized, and describe how an existing method solves this problem. A more efficient algorithm that combines sorting, binary search and graph search is then presented to find the minimax/maximin cut. The time complexity of this algorithm is better than those realized by the existing best known algorithms which is proposed by Corley. Moreover, if the total weight should be minimized, the the complexity of our algorithm is as good as the best known algorithm for the min-cut/max-flow problem. Finally, two examples are given to demonstrate this new algorithm.