On the minimum diameter spanning tree problem

DOI10.1016/0020-0190(94)00183-YzbMath0875.68442OpenAlexW2004681879MaRDI QIDQ673823

Arie Tamir, Refael Hassin

Publication date: 28 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00183-y

zbMATH Keywords

AlgorithmsCombinatorial problemsAbsolute 1-centerMinimum diameter spanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Parallel algorithms in computer science (68W10)

Related Items

Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree, Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs, Light graphs with small routing cost, A 2k-vertex Kernel for Maximum Internal Spanning Tree, Network search games, with arbitrary searcher starting point, The Center Colorıng of a Graph, A sifting-edges algorithm for accelerating the computation of absolute 1-center in graphs, Optimality computation of the minimum stretch spanning tree problem, Bounded-degree minimum-radius spanning trees in wireless sensor networks, Reconfiguration of spanning trees with degree constraints or diameter constraints, Cooperative location games based on the minimum diameter spanning Steiner subgraph problem, A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem, Minimum diameter cost-constrained Steiner trees, Facility location and the geometric minimum-diameter spanning tree., Minimum restricted diameter spanning trees., Network search games with immobile hider, without a designated searcher starting point, Modeling and solving the bi-objective minimum diameter-cost spanning tree problem, Hardness and efficiency on \(t\)-admissibility for graph operations, Algorithms for the minimum diameter terminal Steiner tree problem, Spanning trees with small diameters, Combinatorial network abstraction by trees and distances, The zoo of tree spanner problems, Minimum cut bases in undirected networks, Diameter-preserving spanning trees in sparse weighted graphs, Minimum diameter color-spanning sets revisited, Reload cost problems: Minimum diameter spanning tree, A cooperative location game based on the 1-center location problem, Minimax flow tree problems, Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree, Minimum diameter vertex-weighted Steiner tree, A unifying model for locally constrained spanning tree problems, Delay-constrained minimum shortest path trees and related problems, Delay-constrained minimum shortest path trees and related problems, Strongly polynomial-time truthful mechanisms in one shot, The non-approximability of bicriteria network design problems

Cites Work

• The absolute centre of a graph
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Minimum Diameter Spanning Trees and Related Problems
• The Centers and Medians of a Graph
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• Unnamed Item