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_5MaRDI QIDQ2117617zbMATH OpenOpenAlexFDO

Authors Eh. 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 algorithmasymptotic optimalityprobabilistic analysisgiven-diameter minimum spanning tree

Mathematics Subject Classification ID

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

Recommendations

• A given diameter MST on a random graph
• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• scientific article; zbMATH DE number 1594512
• On edge-disjoint spanning trees with small depths

Cites work

• scientific article; zbMATH DE number 1594512 (Why is no real title available?)
• scientific article; zbMATH DE number 3664741 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 741240 (Why is no real title available?)
• A given diameter MST on a random graph
• A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
• On the length of a random minimum spanning tree
• On the value of a random minimum spanning tree problem
• Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below

Cited in

(3)

• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• A given diameter MST on a random graph
• 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: 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

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