Abstrakt. Prefetching är en grundläggande mekanism för snabbare dataåtkomst och effektiv databehandling. En viktig fråga när det gäller förhämtning är avvägningen mellan mängden nätresurser som slösas bort av förhämtningen och tidsvinsten. På webben kan till exempel webbläsare ladda ner dokument i förväg medan en surfare surfar på webben. Eftersom websurfaren följer hyperlänkarna på ett oförutsägbart sätt, måste valet av webbsidor som ska förhandsberäknas beräknas online. Frågan är då att bestämma den minsta mängd resurser som används genom förhämtning som säkerställer att alla dokument som webbsurfaren har tillgång till tidigare har laddats i cache. Vi modellerar detta problem som en två-spelare spel som liknar Cops och Robber Games i grafer. Den första spelaren, en rymling, börjar på en markerad vertex av en (di)graph G. Den andra spelaren, en observatör, markerar k ≥ 1 hörn, sedan flyktingen flyttar längs en kant/arc av G till en ny vertex, sedan observatören markerar k hörn, etc. Observatören vinner om han hindrar rymlingen att nå en omärkt vertex. Flyktingen vinner annars, d.v.s. om hon lyckas ta sig in i en omärkt vertex. Övervakningsnumret för en (di)graf är det minsta k ≥ 1 som gör det möjligt för observatören att vinna mot någon strategi för rymlingen. Vi studerar spelets computational komplexitet. Vi visar att avgöra om övervakningsnumret för en ackordkurva är lika med 2 är NPhard. Besluta om övervakningsnumret för en DAG är lika med 4 är PSPACEfullständigt. Dessutom, beräkning av övervakningsnumret är NP-hård i delade grafer. Å andra sidan, vi ger polynom tid algoritmer dator övervakning antal träd och intervall grafer. Dessutom, när det gäller träd, etablerar vi en kombinatorisk karakterisering, relaterad till isoperimetri, av övervakningsnumret.
Polynom-tid algoritmer som beräknar övervakningsnumret i träd och intervall grafer är utformade i REF.
To Satisfy Impatient Web surfers is Hard