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

DOI10.1007/S00493-012-2552-ZzbMATH Open1299.05288arXiv0810.4908OpenAlexW3099735866MaRDI QIDQ452816FDOQ452816

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

Publication date: 17 September 2012

Published in: Combinatorica (Search for Journal in Brave)

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)}.

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

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

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)

Cites Work

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

Cited In (7)

• Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics
• 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
• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• The cavity approach for Steiner trees packing problems
• 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
• Maximal Steiner trees in the stochastic mean-field model of distance

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)