### Abstract

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

Original language | English (US) |
---|---|

Pages (from-to) | 411-417 |

Number of pages | 7 |

Journal | Journal of Algorithms |

Volume | 9 |

Issue number | 3 |

DOIs | |

State | Published - Sep 1988 |

### All Science Journal Classification (ASJC) codes

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Algorithms for two bottleneck optimization problems'. Together they form a unique fingerprint.

## Cite this

Gabow, H. N., & Tarjan, R. E. (1988). Algorithms for two bottleneck optimization problems.

*Journal of Algorithms*,*9*(3), 411-417. https://doi.org/10.1016/0196-6774(88)90031-4