The Min-Max Spanning Tree Problem and some extensions

DOI10.1016/0020-0190(78)90030-3zbMath0373.05028OpenAlexW1968182342MaRDI QIDQ1244239

Publication date: 1978

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(78)90030-3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Combinatorial aspects of matroids and geometric lattices (05B35) Algorithms in computer science (68W99)

Related Items

A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem, The Minimum Moving Spanning Tree Problem, On combined minmax-minsum optimization, Partial inverse min-max spanning tree problem, The minimum moving spanning tree problem, Most and least uniform spanning trees, Cuttings for disks and axis-aligned rectangles in three-space, Some inverse min-max network problems under weighted \(l_1\) ans \(l_{\infty}\) norms with bound constraints on changes, Unnamed Item, Online learning for min-max discrete problems, A fast algorithm for a class of bottleneck problems, Constrained matroidal bottleneck problems, On some multicriteria arborescence problems: Complexity and algorithms, On weighting two criteria with a parameter in combinatorial optimization problems, Upgrading min-max spanning tree problem under various cost functions, Partial inverse min-max spanning tree problem under the weighted bottleneck Hamming distance, Arborescence optimization problems solvable by Edmonds' algorithm, A note on upgrading the min–max weight of a base of a matroid, Complexity of spanning tree problems: Part I, Partial inverse min-max spanning tree problem under the weighted bottleneck Hamming distance, Unnamed Item, Possibilistic bottleneck combinatorial optimization problems with ill-known weights, k-sum optimization problems, Inverse min-max spanning tree problem under the weighted sum-type Hamming distance, Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion, Lexicographic balanced optimization problems, The image of weighted combinatorial problems, Quadratic bottleneck problems, Maximum weight archipelago subgraph problem, Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity, A class of bottleneck expansion problems, An efficient heuristic algorithm for the bottleneck traveling salesman problem, An algebraic framework for minimum spanning tree problems, Algorithms for Euclidean Degree Bounded Spanning Tree Problems, Degree bounded bottleneck spanning trees in three dimensions, In memoriam Paolo M. Camerini, The tricriterion shortest path problem with at least two bottleneck objective functions, Euclidean bottleneck bounded-degree spanning tree ratios, Constrained inverse min-max spanning tree problems under the weighted Hamming distance, The partial sum criterion for Steiner trees in graphs and shortest paths, The minimum labeling spanning trees, Bounded-angle minimum spanning trees, The bottleneck \(k\)-MST, Solving the 2-rooted mini-max spanning forest problem by branch-and-bound, Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems, A linear time algorithm for the bottleneck biconnected spanning subgraph problem, Minmax regret solutions for minimax optimization problems with uncertainty, Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making, Solving some lexicographic multi-objective combinatorial problems, Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten bounding, Minimum deviation and balanced optimization: A unified approach, A linear time algorithm for the maximum capacity path problem, Approximate spanning cactus

Cites Work