The Min-Max Spanning Tree Problem and some extensions
From MaRDI portal
Publication:1244239
DOI10.1016/0020-0190(78)90030-3zbMath0373.05028MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
05B35: Combinatorial aspects of matroids and geometric lattices
68W99: Algorithms in computer science
Related Items
Quadratic bottleneck problems, A class of bottleneck expansion problems, Minimum deviation and balanced optimization: A unified approach, A linear time algorithm for the maximum capacity path problem, Cuttings for disks and axis-aligned rectangles in three-space, k-sum optimization problems, Inverse min-max spanning tree problem under the weighted sum-type Hamming distance, Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity, The tricriterion shortest path problem with at least two bottleneck objective functions, Constrained inverse min-max spanning tree problems under the weighted Hamming distance, The bottleneck \(k\)-MST, Solving the 2-rooted mini-max spanning forest problem by branch-and-bound, Most and least uniform spanning trees, Complexity of spanning tree problems: Part I, The image of weighted combinatorial problems, The partial sum criterion for Steiner trees in graphs and shortest paths, A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem, On combined minmax-minsum optimization, Arborescence optimization problems solvable by Edmonds' algorithm, Lexicographic balanced optimization problems, The minimum labeling spanning trees, Minmax regret solutions for minimax optimization problems with uncertainty, Solving some lexicographic multi-objective combinatorial problems, In memoriam Paolo M. Camerini, A linear time algorithm for the bottleneck biconnected spanning subgraph problem, A fast algorithm for a class of bottleneck problems, Constrained matroidal bottleneck problems, On some multicriteria arborescence problems: Complexity and algorithms, An efficient heuristic algorithm for the bottleneck traveling salesman problem, Some inverse min-max network problems under weighted \(l_1\) ans \(l_{\infty}\) norms with bound constraints on changes
Cites Work
- Unnamed Item
- Unnamed Item
- An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
- Finding the median
- Parallel concepts in graph theory
- On the computational power of pushdown automata
- Two Algorithms for Generating Weighted Spanning Trees in Order
- Finding Minimum Spanning Trees
- Finding optimum branchings
- Depth-First Search and Linear Graph Algorithms
