Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem

DOI10.1007/978-3-540-77050-3_41MaRDI QIDQ5458860zbMATH OpenOpenAlexFDO

Authors Anand Srivastav, Sören Werth

Publication date 24 April 2008

Published in FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77050-3_41

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• The vertex degrees of minimum spanning trees
• Degree-bounded minimum spanning trees
• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
• The central limit theorem for Euclidean minimal spanning trees II
• Euclidean bounded-degree spanning tree ratios

Cites work

• A matching problem and subadditive Euclidean functionals
• Approximation schemes for degree-restricted MST and red-blue separation problems
• Asymptotics for geometric location problems over random samples
• Euclidean bounded-degree spanning tree ratios
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• Light Orthogonal Networks with Constant Geometric Dilation
• Limit theorems and rates of convergence for Euclidean functionals
• On two geometric problems related to the travelling salesman problem
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Postulates for subadditive processes
• Probabilistic analysis for a multiple depot vehicle routing problem
• Probability theory of classical Euclidean optimization problems
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• The Existence of Probability Measures with Given Marginals
• Transitions in geometric minimum spanning trees

Cited in

(13)

• Chance constrained bottleneck spanning tree problem
• On the probabilistic min spanning tree problem
• Smoothed analysis of partitioning algorithms for Euclidean functionals
• On the chance-constrained minimum spanning \(k\)-core problem
• DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
• scientific article; zbMATH DE number 5931400 (Why is no real title available?)
• scientific article; zbMATH DE number 1805832 (Why is no real title available?)
• Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below
• The probabilistic minimum spanning tree problem
• Structural Information and Communication Complexity
• Continuous approximation formulas for location problems
• On minimum spanning trees for random Euclidean bipartite graphs
• Cube versus torus models and the Euclidean minimum spanning tree constant

This page was built for publication: Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem

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