Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem

DOI10.1007/978-3-540-77050-3_41zbMath1135.90041OpenAlexW175627016MaRDI QIDQ5458860

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)

Related Items (2)

Continuous approximation formulas for location problems ⋮ Smoothed analysis of partitioning algorithms for Euclidean functionals

Cites Work

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

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