A note on the bottleneck graph partition problem

The bottleneck graph partition problem consists of partitioning the vertice s of an undirected edge-weighted graph into two equally sized sets such tha t the maximum edge weight in the cut separating the two sets becomes minimu m. In this short note, we present an optimum algorithm for this problem wit h running time O(n(2)), where n is the number of vertices in the graph. Our result answers an open problem posed in a recent paper by Hochbaum and Pat hria (1996). (C) 1999 John Wiley & Sons, Inc.