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

DOI10.1007/978-3-030-77876-7_5zbMath1485.05026OpenAlexW3172401377MaRDI QIDQ2117617

E. Kh. Gimadi, Aleksandr S. Shevyakov, Alexandr A. Shtepa

Publication date: 22 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-77876-7_5

zbMATH Keywords

approximation algorithmprobabilistic analysisasymptotic optimalitygiven-diameter minimum spanning tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
• On the value of a random minimum spanning tree problem
• A given diameter MST on a random graph
• Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below
• On the Length of a Random Minimum Spanning Tree

This page was built for publication: 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