MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTETo Satisfy Impatient Web surfers is Hard
par Nicolas Nisse
| Date : | 25/10/11 | | Time : | 10h30 | | Location : | Lagrange Gris |
In the Web, browsers may download documents in advance while an Internaut is sur ng on the Web. Since the web surfer follows the hyperlinks in an unpredictable way, the choice of the web pages to be prefetched must be computed online. The question is then to determine the minimum amount of resources used by prefetching that ensures that all documents accessed by the web surfer have previously been loaded in the cache.
We model this problem as a two-players game similar to Cops and Robber Games in graphs. The fi rst player, a fugitive, starts on a marked vertex of a (di)graph G. The second player, an observer, marks k >0 vertices, then the fugitive moves along one edge/arc of G to a new vertex, then observer marks k vertices, etc. The observer wins if he prevents the fugitive to reach an unmarked vertex. The surveillance number of a graph is the minimum k>0 allowing the observer to win against any strategy of the fugitive.
We give several results on the computational complexity of the game.
Page des séminaires
| 
