Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 16 / Issue 5

available in:   PDF (312 kB) PS (330 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-016-05-0686


Reachability in Restricted Walk on Integers

Philip Ginzboorg (Nokia Research Center, Finland)

Valtteri Niemi (Nokia Research Center, Switzerland)

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: Hamiltonian path, random walk, reachability, shortest path, strong connectivity

Categories: C.3, G.2.2