Rudolf GrÃ¼bel.
The successive discrete structures generated by a sequential algorithm from
random input constitute a Markov chain that may exhibit long term dependence on
its first few input values. Using examples from random graph theory and search
algorithms we show how such persistence of randomness can be detected and
quantified with techniques from discrete potential theory. We also show that
this approach can be used to obtain strong limit theorems in cases where
previously only distributional convergence was known.
Section:
Analysis of Algorithms
Stephan Dominique Andres ; Winfried HochstÃ¤ttler.
We prove that the game colouring number of the $m$-th power of a forest of
maximum degree $\Delta\ge3$ is bounded from above by
\[\frac{(\Delta-1)^m-1}{\Delta-2}+2^m+1,\] which improves the best known bound
by an asymptotic factor of 2.
Section:
Graph Theory