𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on the bottleneck graph partition problem

✍ Scribed by Klinz, Bettina; Woeginger, Gerhard J.

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
47 KB
Volume
33
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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 .

πŸ“œ SIMILAR VOLUMES

The bottleneck graph partition problem
The bottleneck graph partition problem
✍ Hochbaum, Dorit S.; Pathria, Anu πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 401 KB πŸ‘ 1 views

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, th

A note on vertex pancyclic oriented grap
A note on vertex pancyclic oriented graphs
✍ Bang-Jensen, JοΏ½rgen; Guo, Yubao πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 185 KB πŸ‘ 1 views

Let D be an oriented graph of order n β‰₯ 9, minimum degree at least n -2, such that, for the choice of distinct vertices x and y, . Graph Theory 18 (1994), 461-468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also