**The Bottleneck Graph Partition Problem**

## Abstract

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.

## Download Information

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.

`dorit@hochbaum.ieor.berkeley.edu`
7/30/98