Greedy Search on the Binary Tree with Random Edge-Weights

DOI10.1017/S096354830000033XMaRDI QIDQ4291188zbMATH OpenFDO

Authors David Aldous

Publication date 5 May 1994

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

Full work available at URL https://doi.org/10.1017/S096354830000033X

zbMATH Keywords

binary treegreedy algorithmsearching

Mathematics Subject Classification ID

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

Recommendations

• Searches on a Binary Tree with Random Edge-Weights
• A Greedy Algorithm Estimating the Height of Random Trees
• scientific article; zbMATH DE number 3858430
• The Greedy Search Algorithm on Binary Vectors
• A Metropolis-type optimization algorithm on the infinite tree

Cites work

• A branching random walk with a barrier
• A fixed point theorem for distributions
• A path decomposition for Markov processes
• Chernoff's theorem in the branching random walk
• Discounted branching random walks
• Fixed points of the smoothing transformation
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 3223982 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Probability metrics and recursive algorithms
• Random walk in a random environment and first-passage percolation on trees
• Random walks on a tree and capacity in the interval
• Searching for an optimal path in a tree with random costs
• The \(3x +1\) problem: Two stochastic models

Cited in

(11)

• A Metropolis-type optimization algorithm on the infinite tree
• Efficient approximation of branching random walk Gibbs measures
• On a problem of Erdös and Taylor
• An almost-greedy search on random binary vectors and random graphs
• The Greedy Search Algorithm on Binary Vectors
• Optimal reward on a sparse tree with random edge weights
• Searches on a Binary Tree with Random Edge-Weights
• A survey of max-type recursive distributional equations
• Yaglom-type limit theorems for branching Brownian motion with absorption
• Total progeny in killed branching random walk
• Search cost for a nearly optimal path in a binary tree

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

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