Greedy Search on the Binary Tree with Random Edge-Weights

DOI10.1017/S096354830000033XzbMath0803.68025MaRDI QIDQ4291188

David J. Aldous

Publication date: 5 May 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

binary treegreedy algorithmsearching

Mathematics Subject Classification ID

Trees (05C05) Searching and sorting (68P10) Sums of independent random variables; random walks (60G50) Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

Search cost for a nearly optimal path in a binary tree ⋮ Efficient approximation of branching random walk Gibbs measures ⋮ Optimal reward on a sparse tree with random edge weights ⋮ Yaglom-type limit theorems for branching Brownian motion with absorption ⋮ Total progeny in killed branching random walk ⋮ A survey of max-type recursive distributional equations ⋮ On a problem of Erdös and Taylor

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A branching random walk with a barrier
• Random walk in a random environment and first-passage percolation on trees
• The \(3x +1\) problem: Two stochastic models
• A fixed point theorem for distributions
• Random walks on a tree and capacity in the interval
• A path decomposition for Markov processes
• Searching for an optimal path in a tree with random costs
• Chernoff's theorem in the branching random walk
• Fixed points of the smoothing transformation
• Probability metrics and recursive algorithms
• Discounted branching random walks

This page was built for publication: Greedy Search on the Binary Tree with Random Edge-Weights