Search cost for a nearly optimal path in a binary tree
From MaRDI portal
Publication:835059
DOI10.1214/08-AAP585zbMath1176.68093arXivmath/0701741OpenAlexW3102782178MaRDI QIDQ835059
Publication date: 27 August 2009
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0701741
algorithmcomputational complexityminimal displacementoptimal pathbranching random walkmaximal displacement
Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)
Related Items (8)
Efficient approximation of branching random walk Gibbs measures ⋮ The algorithmic hardness threshold for continuous random energy models ⋮ The critical barrier for the survival of branching random walk with absorption ⋮ Asymptotics for the survival probability in a killed branching random walk ⋮ The genealogy of branching Brownian motion with absorption ⋮ Total progeny in killed branching random walk ⋮ Brunet-Derrida behavior of branching-selection particle systems on the line ⋮ Survival of branching random walks with absorption
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Postulates for subadditive processes
- Subadditive ergodic theory
- The first birth problem for an age-dependent branching process
- Branching Brownian motion with absorption
- A Metropolis-type optimization algorithm on the infinite tree
- Searching for an optimal path in a tree with random costs
- Survival probabilities for branching Brownian motion with absorption
- Further probabilistic analysis of the Fisher-Kolmogorov-Petrovskii-Piscounov equation: one sided travelling-waves
- Supercritical Branching Brownian Motion and K-P-P Equation In the Critical Speed-Area
- Maximal displacement of branching brownian motion
- Minimal displacement of branching random walk
- Chernoff's theorem in the branching random walk
- Greedy Search on the Binary Tree with Random Edge-Weights
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
This page was built for publication: Search cost for a nearly optimal path in a binary tree
