Algorithms for Two Bottleneck Optimization Problems

A bottleneck optimization 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 f 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{log n+m, m log* n} -time algorithm. For the bottleneck maximum cardinality matching problem, we propose an O((n log n) 1/2 m)-time algorithm.