Name
Abstract | ||
|---|---|---|
The surveillance game [4] models the problem of web-page prefetching as a pursuit evasion game played on a graph. This two-player game is played turn-by-turn. The first player, called the observer, can mark a fixed amount of vertices at each turn. The second one controls a surfer that stands at vertices of the graph and can slide along edges. The surfer starts at some initially marked vertex of the graph, its objective is to reach an unmarked node before all nodes of the graph are marked. The surveillance number sn(G) of a graph G is the minimum amount of nodes that the observer has to mark at each turn ensuring it wins against any surfer in G. Fomin et al. also defined the connected surveillance game where the observer must ensure that marked nodes always induce a connected subgraph. They ask what is the cost of connectivity, i.e., is there a constant c>0 such that the ratio between the connected surveillance number csn(G) and sn(G) is at most c for any graph G. It is straightforward to show that csn(G)≤Δsn(G) for any graph G with maximum degree Δ. Moreover, it has been shown that there are graphs G for which csn(G)=sn(G)+1. In this paper, we investigate the question of the cost of the connectivity. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.tcs.2014.11.025 | Theoretical Computer Science |
Keywords | DocType | Volume |
Surveillance game,Cops and robber games,Cost of connectivity,Online strategy,Competitive ratio,Prefetching | Journal | 584 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
7 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frédéric Giroire | 1 | 194 | 22.80 |
| I. Lamprou | 2 | 0 | 1.01 |
| Dorian Mazauric | 3 | 82 | 13.34 |
| Nicolas Nisse | 4 | 313 | 32.82 |
| Stéphane Pérennes | 5 | 223 | 23.08 |
| R. Soares | 6 | 0 | 0.34 |