Algorithms for two bottleneck optimization problems

Harold N. Gabow, Robert E. Tarjan

Research output: Contribution to journalArticle

113 Scopus citations

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 2m)-time algorithm.

Original languageEnglish (US)
Pages (from-to)411-417
Number of pages7
JournalJournal of Algorithms
Volume9
Issue number3
DOIs
StatePublished - 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