Article ID: | iaor2002370 |
Country: | United States |
Volume: | 28 |
Issue: | 4 |
Start Page Number: | 221 |
End Page Number: | 225 |
Publication Date: | Dec 1996 |
Journal: | Networks |
Authors: | Hochbaum Dorit S., Pathria Anu |
Keywords: | bottlenecks |
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