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_5zbMATH Open1485.05026OpenAlexW3172401377MaRDI QIDQ2117617FDOQ2117617

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the value of a random minimum spanning tree problem
• A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
• Title not available (Why is that?)
• Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below
• On the Length of a Random Minimum Spanning Tree
• A given diameter MST on a random graph

Cited In (2)

• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• A given diameter MST on a random graph

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)