Algorithms for two bottleneck optimization problems
From MaRDI portal
Publication:3799842
DOI10.1016/0196-6774(88)90031-4zbMath0653.90087OpenAlexW1988114663WikidataQ60488526 ScholiaQ60488526MaRDI QIDQ3799842
Harold N. Gabow, Robert Endre Tarjan
Publication date: 1988
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://zenodo.org/record/1258419
directed graphsubgraphbottleneck optimizationbottleneck maximum cardinality matching problembottleneck spannig treegraph with edge costs
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)
Related Items (61)
A greedy and distributable approach to the Lexicographic Bottleneck Assignment Problem with conditions on exactness ⋮ Improved complexity bound for the maximum cardinality bottleneck bipartite matching problem ⋮ A stronger lower bound on parametric minimum spanning trees ⋮ On Element-Connectivity Preserving Graph Simplification ⋮ An Oracle Strongly Polynomial Algorithm for Bottleneck Expansion Problems ⋮ A heuristic for decomposing traffic matrices in TDMA satellite communication ⋮ Serve or skip: the power of rejection in online bottleneck matching ⋮ Unnamed Item ⋮ Online learning for min-max discrete problems ⋮ A fast algorithm for a class of bottleneck problems ⋮ Solution methods and computational investigations for the linear bottleneck assignment problem ⋮ A linear time algorithm for the \(r\)-gathering problem on the line ⋮ The dominance assignment problem ⋮ Unnamed Item ⋮ Uniform machine scheduling of unit-time jobs subject to resource constraints ⋮ The random linear bottleneck assignment problem ⋮ Bottleneck matching in the plane ⋮ Arborescence optimization problems solvable by Edmonds' algorithm ⋮ Algebraic theory on shortest paths for all flows ⋮ Bottleneck partial-matching Voronoi diagrams and applications ⋮ Proportionate flowshops with general position-dependent processing times ⋮ Higher-order triangular-distance Delaunay graphs: graph-theoretical properties ⋮ All-pairs bottleneck paths in vertex weighted graphs ⋮ Possibilistic bottleneck combinatorial optimization problems with ill-known weights ⋮ Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems ⋮ Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion ⋮ The \(k\)-centrum Chinese postman delivery problem and a related cost allocation game ⋮ Quadratic bottleneck problems ⋮ Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs. ⋮ A stronger lower bound on parametric minimum spanning trees ⋮ Some results concerning the complexity of restricted colorings of graphs ⋮ Forests, frames, and games: Algorithms for matroid sums and applications ⋮ Linear independence in bottleneck algebras ⋮ Path-matching problems ⋮ Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs ⋮ Random assignment problems ⋮ Preconditioning techniques based on the Birkhoff-von Neumann decomposition ⋮ Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity ⋮ Selected topics on assignment problems ⋮ The algebraic Monge property and path problems ⋮ A class of bottleneck expansion problems ⋮ Algebraic Theory on Shortest Paths for All Flows ⋮ Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs ⋮ Bottleneck flows in unit capacity networks ⋮ An efficient heuristic algorithm for the bottleneck traveling salesman problem ⋮ Minmax scheduling and due-window assignment with position-dependent processing times and job rejection ⋮ An efficient algorithm for the Steiner tree problem with revenue, bottleneck and hop objective functions ⋮ Transitive blocks and their applications in fuzzy interconnection networks ⋮ Trapezoidal matrices and the bottleneck assignment problem ⋮ Deterministic Graphical Games Revisited ⋮ The tricriterion shortest path problem with at least two bottleneck objective functions ⋮ On some matching problems under the color-spanning model ⋮ A Simple Algorithm for $r$-gatherings on the Line ⋮ The bottleneck \(k\)-MST ⋮ Improved polynomial algorithms for robust bottleneck problems with interval data ⋮ Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems ⋮ The stochastic bottleneck linear programming problem ⋮ On the weak robustness of interval fuzzy matrices ⋮ An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices ⋮ Strong regularity of matrices -- a survey of results ⋮ Computing Euclidean bottleneck matchings in higher dimensions
This page was built for publication: Algorithms for two bottleneck optimization problems
