On a Random Walk Survivability problem with arc failures and memory

Burak Büke, J. Cole Smith, Sadie Thomas

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Consider a directed network in which each arc can fail with some specified probability. An entity arrives on this network at a designated origin node and traverses the network in a random-walk fashion until it either terminates at a destination node, or until an arc fails while being traversed. We study the problem of assessing the probability that the random walk reaches the destination node, which we call the survival probability of the network. Complicating our analysis is the assumption that certain arcs have "memory," in the sense that after a memory arc is successfully traversed, it cannot fail on any subsequent traversal during the walk. We prove that this problem is #P-hard, provide methods for obtaining lower and upper bounds on the survival probability, and demonstrate the effectiveness of our bounding methods on randomly generated networks.

Original languageEnglish (US)
Pages (from-to)67-86
Number of pages20
JournalNetworks
Volume66
Issue number1
DOIs
StatePublished - Aug 1 2015

Keywords

  • #P-hard
  • Markov chain
  • computational complexity
  • heuristics
  • network reliability
  • random walks on graphs
  • survival probability

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'On a Random Walk Survivability problem with arc failures and memory'. Together they form a unique fingerprint.

Cite this