HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

To Satisfy Impatient Web surfers is Hard

Fedor V. 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 , Laboratoire I3S - 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.
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Wednesday, December 21, 2011 - 1:20:47 PM
Last modification on : Sunday, May 1, 2022 - 3:14:39 AM
Long-term archiving on: : Thursday, March 30, 2017 - 9:04:53 PM


Files produced by the author(s)


  • HAL Id : inria-00625703, version 2


Fedor V. 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⟩



Record views


Files downloads