Premium
A note on the bottleneck graph partition problem
Author(s) -
Klinz Bettina,
Woeginger Gerhard J.
Publication year - 1999
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(199905)33:3<189::aid-net5>3.0.co;2-2
Subject(s) - bottleneck , combinatorics , partition (number theory) , graph partition , mathematics , graph , strength of a graph , undirected graph , discrete mathematics , computer science , line graph , graph power , embedded system
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 2 ), 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 (1996). © 1999 John Wiley & Sons, Inc. Networks 33: 189–191, 1999