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 , 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.
Type de document :
Article dans une revue
Journal of Theoretical Computer Science (TCS), Elsevier, 2014, 526, pp.1-17. <10.1016/j.tcs.2014.01.009>
Contributeur : Nicolas Nisse <>
Soumis le : jeudi 27 mars 2014 - 16:29:25
Dernière modification le : jeudi 9 février 2017 - 15:47:15
Document(s) archivé(s) le : vendredi 27 juin 2014 - 12:40:46


Fichiers produits par l'(les) auteur(s)




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



Consultations de
la notice


Téléchargements du document