A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

DOI10.1007/S00493-012-2552-ZMaRDI QIDQ452816zbMATH OpenOpenAlexFDO

Authors Omer Angel, Abraham D. Flaxman, David B. Wilson

Publication date 17 September 2012

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0810.4908

zbMATH Keywords

bounded diameterspanning treeSteiner treebounded depth

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25) Combinatorial probability (60C05) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Abstract: In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to zeta(3)=1/1^3+1/2^3+1/3^3+... as n goes to infinity. We consider spanning trees constrained to have depth bounded by k from a specified root. We prove that if k > log_2 log n+omega(1), where omega(1) is any function going to infinity with n, then the minimum bounded-depth spanning tree still has weight tending to zeta(3) as n -> infinity, and that if k < log_2 log n, then the weight is doubly-exponentially large in log_2 log n - k. It is NP-hard to find the minimum bounded-depth spanning tree, but when k < log_2 log n - omega(1), a simple greedy algorithm is asymptotically optimal, and when k > log_2 log n+omega(1), an algorithm which makes small changes to the minimum (unbounded depth) spanning tree is asymptotically optimal. We prove similar results for minimum bounded-depth Steiner trees, where the tree must connect a specified set of m vertices, and may or may not include other vertices. In particular, when m = const * n, if k > log_2 log n+omega(1), the minimum bounded-depth Steiner tree on the complete graph has asymptotically the same weight as the minimum Steiner tree, and if 1 <= k <= log_2 log n-omega(1), the weight tends to (1-2^{-k}) sqrt{8m/n} [sqrt{2mn}/2^k]^{1/(2^k-1)} in both expectation and probability. The same results hold for minimum bounded-diameter Steiner trees when the diameter bound is 2k; when the diameter bound is increased from 2k to 2k+1, the minimum Steiner tree weight is reduced by a factor of 2^{1/(2^k-1)}.

Recommendations

• Sharp threshold for the appearance of certain spanning trees in random graphs
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• scientific article; zbMATH DE number 3985248
• scientific article; zbMATH DE number 1984546
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• Bounding Distributions for the Weight of a Minimum Spanning Tree in Stochastic Networks
• Stochastic bounded diameter minimum spanning tree problem
• Approximating minimum bounded degree spanning trees to within one of optimal
• Minimum congestion spanning trees in bipartite and random graphs

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 91018 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 540118 (Why is no real title available?)
• scientific article; zbMATH DE number 1439494 (Why is no real title available?)
• Approximating \(k\)-hop minimum-spanning trees
• Approximating the weight of shallow Steiner trees
• Critical random graphs and the structure of a minimum spanning tree
• Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints
• Generalized submodular cover problems and applications
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
• Multicommodity flow models for spanning trees with hop constraints
• Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
• On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees
• On formulations and methods for the hop-constrained minimum spanning tree problem
• On random minimum length spanning trees
• On the bounded-hop MST problem on random Euclidean instances
• On the height of trees
• On the value of a random minimum spanning tree problem
• On the value of a random minimum weight Steiner tree
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Random-tree Diameter and the Diameter-constrained MST
• Scaling and universality in continuous length combinatorial optimization
• The Steiner tree problem with hop constraints
• The maximum \(f\)-depth spanning tree problem
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints

Cited in

(7)

• Maximal Steiner trees in the stochastic mean-field model of distance
• The cavity approach for Steiner trees packing problems
• On asymptotically optimal approach for the problem of finding several edge-disjoint spanning trees of given diameter in an undirected graph with random edge weights
• Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• On the value of a random minimum weight Steiner tree
• On asymptotically optimal approach for finding of the minimum total weight of edge-disjoint spanning trees with a given diameter

This page was built for publication: A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q452816)