Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below

DOI10.1134/S1990478915040043zbMath1349.90711OpenAlexW2300032770MaRDI QIDQ3186835

E. Kh. Gimadi, E. Yu. Shin

Publication date: 12 August 2016

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1990478915040043

zbMATH Keywords

probabilistic analysisspanning treepolynomial algorithmasymptotic optimalityperformance estimate of an algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Stochastic programming (90C15) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

On asymptotically optimal approach for finding of the minimum total weight of edge-disjoint spanning trees with a given diameter, 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

Cites Work

• Spanning trees: A survey
• Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design
• The probabilistic minimum spanning tree problem
• The complexity of the network design problem
• Greedy heuristics for the bounded diameter minimum spanning tree problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item