๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The bottleneck graph partition problem

โœ Scribed by Hochbaum, Dorit S.; Pathria, Anu

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
401 KB
Volume
28
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

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(n2 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. 8 7996 John Wiby & Sons, Inc.

๐Ÿ“œ SIMILAR VOLUMES

A note on the bottleneck graph partition
A note on the bottleneck graph partition problem
โœ Klinz, Bettina; Woeginger, Gerhard J. ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 47 KB ๐Ÿ‘ 2 views

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 wit

The spectrum problem for the Petersen gr
The spectrum problem for the Petersen graph
โœ Adams, Peter; Bryant, Darryn E. ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 305 KB ๐Ÿ‘ 1 views

It is shown that there exists a decomposition of K,, into edge-disjoint copies of the Petersen graph if and only if 'u = 1 or 10 (mod 151, 'u # 10.

The tree center problems and the relatio
The tree center problems and the relationship with the bottleneck knapsack problems
โœ Shioura, Akiyoshi; Shigeno, Maiko ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 57 KB ๐Ÿ‘ 1 views

The tree center problems are designed to find a subtree minimizing the maximum distance from any vertex. This paper shows that these problems in a tree network are related to the bottleneck knapsack problems and presents linear-time algorithms for the tree center problems by using the relation.