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
I3S - Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis, CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Document type :
Reports
[Research Report] RR-7740, LIRMM; INRIA. 2011, pp.20


https://hal.inria.fr/inria-00625703
Contributor : Nicolas Nisse <>
Submitted on : Wednesday, December 21, 2011 - 1:20:47 PM
Last modification on : Tuesday, May 19, 2015 - 1:09:55 AM

File

RR-7740.pdf
fileSource_public_author

Identifiers

  • HAL Id : inria-00625703, version 2

Collections

Citation

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>

Export

Share

Metrics

Consultation de
la notice

220

Téléchargement du document

125