Quick links

Algorithms for Two Bottleneck Optimization Problems

Report ID:
April 1987
Download Formats:


A bottleneck optimization problem on a graph with edge costs is the problem of finding a subgraph of a certain kind that minimizes the maximum edge cost in the subgraph. The bottleneck objective contrasts with the more common objective of minimizing the sum of edge costs. We propose fast algorithms for two
bottleneck optimization problems. For the problem of finding a bottleneck spanning tree in a directed graph of n vertices and m edges, we propose an O(min{n log n + m, mlog* n})-time algorithm. For the bottleneck maximum cardinality matching problem, we propose an O((n log n)1/2m)-time algorithm.

Follow us: Facebook Twitter Linkedin