JUCS - Journal of Universal Computer Science 16(5): 686-714, doi: 10.3217/jucs-016-05-0686
Reachability in Restricted Walk on Integers
expand article infoPhilip Ginzboorg‡, Valtteri Niemi§
‡ Nokia Research Center, Helsinki, Finland§ Nokia Research Center, Lausanne, Switzerland

Corresponding author: Philip Ginzboorg ( philip.ginzboorg@nokia.com )

© Philip Ginzboorg, Valtteri Niemi.
This article is freely available under the J.UCS Open Content License.
Citation: Ginzboorg P, Niemi V (2010) Reachability in Restricted Walk on Integers. JUCS - Journal of Universal Computer Science 16(5): 686-714. https://doi.org/10.3217/jucs-016-05-0686
Open Access
Abstract
We prove that two conditions are sufficient, and with three exceptions also necessary, for reachability of any position in restricted walk on integers in which the sizes of the moves to the left and to the right are constant but need not be equal. A method to compute the length of the shortest path between any two positions, as well as a shortest path algorithm when the reachability conditions are true are given. Also a complete characterization for Hamiltonian restricted walks between absorbing boundaries is given.
Keywords
reachability, random walk, shortest path, Hamiltonian path, strong connectivity