A NEW UNIFYING HEURISTIC ALGORITHM FOR THE UNDIRECTED MINIMUM CUT PROBLEMS USING MINIMUM RANGE CUT ALGORITHMS

Given a connected undirected multigraph with n vertices and m edges, w e first propose a new unifying heuristic approach to approximately sol ving the minimum cut and the s-t minimum cut problems by using efficie nt algorithms for the corresponding minimum range cut problems. Our me thod is based on the association of the range value of a cut and its c ut value when each edge weight is chosen uniformly randomly from the B red interval. Our computational experiments demonstrate that this appr oach produces very good approximate solutions. We shall also propose a n O(log(2) n) time parallel algorithm using O(n(2)) processors on an a rbitrary CRCW PRAM model for the minimum range cut problems, by which we can efficiently obtain approximate minimum cuts in poly-log time us ing a polynomial number of processors.