Analysis of Steiner subtrees of random trees for traceroute algorithms

DOI10.1002/RSA.20263MaRDI QIDQ3055772zbMATH OpenOpenAlexFDO

Authors Fabrice M. Guillemin, Philippe Robert

Publication date 9 November 2010

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20263

zbMATH Keywords

random treesnetwork discovery problemtraceroute algorithm

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• scientific article; zbMATH DE number 3985248
• On the value of a random minimum weight Steiner tree
• Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in R^d
• Stochastic Steiner Tree with Non-uniform Inflation
• Steiner tree approximation via iterative randomized rounding
• Automata, Languages and Programming
• scientific article; zbMATH DE number 2073988
• scientific article; zbMATH DE number 1834686
• Approximating rooted Steiner networks

Cites work

• A probabilistic analysis of some tree algorithms
• Distribution of distances in random binary search trees.
• Distribution of the Steiner Distance in Generalized M-ary Search Trees
• On the asymptotic behavior of some algorithms
• Spanning tree size in random binary search trees.
• The oscillatory distribution of distances in random tries

Cited in

(2)

• Topology discovery of sparse random graphs with few participants
• Steiner distances in generalized corona products

This page was built for publication: Analysis of Steiner subtrees of random trees for traceroute algorithms

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