To Satisfy Impatient Web surfers is Hard

Fedor Fomin 1 Frédéric Giroire 2 Alain Jean-Marie 3, 4 Dorian Mazauric 2 Nicolas Nisse 2
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
4 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Prefetching is a basic mechanism to avoid to waste time when accessing data. However, a tradeoff must be established 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 an Internaut is surfing 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 and that ensures that all documents accessed by the web surfer have previously been loaded in the cache. We model this problem as a game similar to Cops and Robber Games in graphs. A fugitive starts on a marked vertex of a (di)graph G. Turn by turn, an observer marks at most k >= 1 vertices and then the fugitive can move along one edge/arcs of G. The observer wins if he prevents the fugitive to reach an unmarked vertex. The fugitive wins otherwise, i.e., if she enters an unmarked vertex. The surveillance number of a graph is the least k >=1 allowing the observer to win whatever the fugitive does. 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. All our results hold for both variants, connected or not. We show that deciding whether the surveillance number of a chordal graph equals 2 is NP-hard. Deciding if the surveillance number of a DAG equals 4 is PSPACE-complete. Moreover, computing the surveillance number is NP-hard in split graphs. On the other hand, we provide polynomial time algorithms to compute surveillance number of trees and interval graphs. Moreover, in the case of trees, we establish a combinatorial characterization, related to isoperimetry, of the surveillance number.
Type de document :
[Research Report] RR-7740, LIRMM; INRIA. 2011, pp.20
Liste complète des métadonnées
Contributeur : Nicolas Nisse <>
Soumis le : mercredi 21 décembre 2011 - 13:20:47
Dernière modification le : vendredi 9 juin 2017 - 10:42:48
Document(s) archivé(s) le : jeudi 30 mars 2017 - 21:04:53


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


  • HAL Id : inria-00625703, version 2



Fedor Fomin, Frédéric Giroire, Alain Jean-Marie, Dorian Mazauric, Nicolas Nisse. To Satisfy Impatient Web surfers is Hard. [Research Report] RR-7740, LIRMM; INRIA. 2011, pp.20. <inria-00625703v2>



Consultations de
la notice


Téléchargements du document