Premium
The bottleneck graph partition problem
Author(s) -
Hochbaum Dorit S.,
Pathria Anu
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199612)28:4<221::aid-net6>3.0.co;2-n
Subject(s) - bottleneck , combinatorics , partition (number theory) , graph partition , mathematics , bounded function , frequency partition of a graph , graph , discrete mathematics , time complexity , computer science , line graph , graph power , mathematical analysis , embedded system
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 2 log n ) 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. © 1996 John Wiley & Sons, Inc.