TimeVarying Graph Patrolling Against Attackers with Locally Limited and Imperfect Observation Models The use of autonomous robots for surveillance is one of the most interesting applications of graphpatrolling algorithms. In recent years, considerable effort has been devoted to tackling the problem of efficiently computing effective patrolling strategies. One of the mainstream approaches is adversarial patrolling, where a model of a strategic attacker is explicitly taken into account. A common assumption made by these techniques is to consider a worstcase attacker, characterized by ubiquitous and perfect observation capabilities. Motivated by the domain of robotic applications, we instead consider a more realistic and limited attacker model capable of gathering noisy observations in a locally limited range of the environment. We assume that the modeled attacker follows a behavior induced by its observations. Thus, we devise a randomized patrolling strategy based on Markov chains that makes observations reveal very little information, while still maintaining a reasonable level of protection in the environment. Our experimental results obtained in simulation confirm timevariance as a practical approach for our objective.

Cover Time in EdgeUniform StochasticallyEvolving Graphs We define a general model of stochasticallyevolving graphs, namely the edgeuniform stochasticallyevolving graphs. In this model, each possible edge of an underlying general static graph evolves independently being either alive or dead at each discrete time step of evolution following a (Markovian) stochastic rule. The stochastic rule is identical for each possible edge and may depend on the past     k xe2x89xa5 0     observations of the edgexe2x80x99s state. We examine two kinds of random walks for a single agent taking place in such a dynamic graph: (i) The Random Walk with a Delay (RWD), where at each step, the agent chooses (uniformly at random) an incident possible edge, i.e., an incident edge in the underlying static graph, and then, it waits till the edge becomes alive to traverse it. (ii) The more natural Random Walk on what is Available (RWA), where the agent only looks at alive incident edges at each time step and traverses one of them uniformly at random. Our study is on bounding the cover time, i.e., the expected time until each node is visited at least once by the agent. For RWD, we provide a first upper bound for the cases     k  0 , 1     by correlating RWD with a simple random walk on a static graph. Moreover, we present a modified electrical network theory capturing the     k  0     case. For RWA, we derive some first bounds for the case     k  0    , by reducing RWA to an RWDequivalent walk with a modified delay. Further, we also provide a framework that is shown to compute the exact value of the cover time for a general family of stochasticallyevolving graphs in exponential time. Finally, we conduct experiments on the cover time of RWA in edgeuniform graphs and compare the experimental findings with our theoretical bounds.