The Bottleneck Graph Partition Problem
The bottleneck graph partition problem is to partition the nodes of
a graph into two equally sized sets, so that the maximum
edge weight in the cut separating the two sets is minimum.
Whereas the graph partition problem, where the sum of the edge
weights in the cut is to be minimized, is NP-hard, the bottleneck
version is polynomial.
This paper describes an O(n logn) algorithm for the bottleneck
graph partition problem, where n is the number of nodes in the graph.
We point out two interesting issues related to dynamic algorithms.
We also generalize our polynomiality result (for fixed k) to the bottleneck
k-cut problem with specified vertices and bounded components.
Click on the following title to view and download the paper in PostScript format.
- The Bottleneck Graph Partition Problem (8 pages, 104 KB),
- Dorit S. Hochbaum and Anu Pathria. Networks. 28:4, Dec 1996, 221-225.