Edge-disjoint spanning trees of arbitrary bounded diameter on random inputs

DOI10.15826/UMJ.2025.2.007MaRDI QIDQ6841426zbMATH OpenFDO

Authors Eh. Kh. Gimadi, O. Yu. Tsidulko

Publication date 20 March 2026

Published in Unnamed Author (Search for Journal in Brave)

Full work available at URL https://doi.org/10.15826/UMJ.2025.2.007

zbMATH Keywords

bounded diameterprobabilistic analysisedge-disjoint spanning treesasymptotically optimal algorithmrandom inputs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Distance in graphs (05C12) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites work

• scientific article; zbMATH DE number 741240 (Why is no real title available?)
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• 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
• Finding bounded diameter minimum spanning tree in general graphs
• Generalized submodular cover problems and applications
• Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
• On asymptotically optimal approach for finding of the minimum total weight of edge-disjoint spanning trees with a given diameter
• On asymptotically optimal approach to the m-Peripatetic Salesman problem on random inputs
• On some probability inequalities for some discrete optimization problems
• On the shortest spanning subtree of a graph and the traveling salesman problem
• 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
• Several edge-disjoint spanning trees with given diameter in a graph with random discrete edge weights
• Über ein Minimalproblem.

This page was built for publication: Edge-disjoint spanning trees of arbitrary bounded diameter on random inputs

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