 |
|
|
|
|
|
|
|
|
|
|
|
The
following cases are tractable by extended analysis:
|
|
|
| - |
Several random walks in parallel
|
|
product formula for the probability that
independent trials miss a node
|
|
|
| - |
Random walk without step back (except for nodes of degree 1)
|
|
increased state space for analysis: network
edges instead of nodes,
|
|
but the run time complexity is
unchanged
|
|
|
| - |
Random walk followed by flooding on
distance d after the last step
|
extend absorbing state to the set of all
neighbors up to distance d
|
|
|
| - |
Random walk search for replicated data on
n nodes
|
|
use a set of n absorbing states or
|
|
assume a binomial distributed hit
count based on single node search
|
|