Skip to Main content Skip to Navigation
New interface
Journal articles

To satisfy impatient Web surfers is hard

Fedor V. Fomin 1 Frédéric Giroire 2 Alain Jean-Marie 3, 4 Dorian Mazauric 5 Nicolas Nisse 2 
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
4 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
5 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : Prefetching is a basic mechanism for faster data access and efficient computing. An important issue in prefetching is the tradeoff between the amount of network's resources wasted by the prefetching and the gain of time. For instance, in the Web, browsers may download documents in advance while a Web surfer is surfing. 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 theWeb surfer have previously been loaded in the cache. We model this problem as a two-player game similar to Cops and Robber Games in graphs. Let k 1 be any integer. The first player, a fugitive, starts on a marked vertex of a (di)graph G. The second player, an observer, marks at most k vertices, then the fugitive moves along one edge/arc of G to a new vertex, then the observer marks at most k vertices, etc. The fugitive wins if it enters an unmarked vertex, and the observer wins otherwise. The surveillance number of a (di)graph is the minimum k such that the observer marking at most k vertices at each step can win against any strategy of the fugitive. We also consider the connected variant of this game, i.e., when a vertex can be marked only if it is adjacent to an already marked vertex. We study the computational complexity of the game. All our results hold for both variants, connected or unrestricted. We show that deciding whether the surveillance number of a chordal graph is at most 2 is NP-hard. We also prove that deciding if the surveillance number of a DAG is at most 4 is PSPACEcomplete. Moreover, we show that the problem of computing the surveillance number is NP-hard in split graphs. On the other hand, we provide polynomial time algorithms computing surveillance numbers of trees and interval graphs. Moreover, in the case of trees, we establish a combinatorial characterization of the surveillance number.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Thursday, March 27, 2014 - 4:29:25 PM
Last modification on : Wednesday, October 26, 2022 - 4:00:39 AM
Long-term archiving on: : Friday, June 27, 2014 - 12:40:46 PM


Files produced by the author(s)



Fedor V. Fomin, Frédéric Giroire, Alain Jean-Marie, Dorian Mazauric, Nicolas Nisse. To satisfy impatient Web surfers is hard. Theoretical Computer Science, 2014, 526, pp.1-17. ⟨10.1016/j.tcs.2014.01.009⟩. ⟨hal-00966985⟩



Record views


Files downloads