Reachability in restricted walk on integers

Philip Ginzboorg*, Valtteri Niemi

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Pages (from-to)686-714
Number of pages29
JournalJournal of Universal Computer Science
Volume16
Issue number5
DOIs
Publication statusPublished - 2010
MoE publication typeA1 Journal article-refereed

Keywords

  • Hamiltonian path
  • Random walk
  • Reachability
  • Shortest path
  • Strong connectivity

Fingerprint

Dive into the research topics of 'Reachability in restricted walk on integers'. Together they form a unique fingerprint.

Cite this