A note on the bottleneck graph partition problem

The bottleneck graph partition problem consists of partitioning the vertices of an undirected edge-weighted graph into two equally sized sets such that the maximum edge weight in the cut separating the two sets becomes minimum. In this short note, we present an optimum algorithm for this problem with running time O(n²), where n is the number of vertices in the graph. Our result answers an open problem posed in a recent paper by Hochbaum and Pathria.