scientific article; zbMATH DE number 15993

MaRDI QIDQ3972640zbMATH OpenFDO

Authors Colin McDiarmid

Publication date 25 June 1992

zbMATH Keywords

age-dependent branching processalgorithmsfirst birth

Mathematics Subject Classification ID

Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Applications of branching processes (60J85)

Review text

[For the entire collection see Zbl 0714.00019.] Suppose the birth times in an age-dependent branching process correspond to the cost of the associated node in the family tree. Finding the first birth in the \(n\)-th generation then corresponds to finding the cheapest node of depth \(n\). This paper studies certain algorithms for finding a node of (nearly) optimal cost of depth \(n\). Naturally the paper draws heavily on known results for the age-dependent branching process, in particular on the results of \textit{J. F. C. Kingman} [Ann. of Probab. 3, 790-801 (1975; Zbl 0325.60079)].

Recommendations

• scientific article; zbMATH DE number 1334602
• The age structure of nodes in Markov random branching tree
• scientific article; zbMATH DE number 3853098
• Branching processes and their applications in the analysis of tree structures and tree algorithms
• A probabilistic analysis of some tree algorithms

Cited in

(11)

• Probabilistic analysis of vantage point trees
• A study of complexity transitions on the asymmetric traveling salesman problem
• Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
• The age structure of nodes in Markov random branching tree
• scientific article; zbMATH DE number 3932819 (Why is no real title available?)
• scientific article; zbMATH DE number 2100534 (Why is no real title available?)
• Probabilistic analysis of an election algorithm in a tree
• Performance of linear-space search algorithms
• Performance of linear-space search algorithms
• Iterative state-space reduction for flexible computation
• Average-case analysis of best-first search in two representative directed acyclic graphs

This page was built for publication:

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