To satisfy impatient web surfers is hard

DOI10.1016/J.TCS.2014.01.009zbMATH Open1282.68082DBLPjournals/tcs/FominGJMN14OpenAlexW2084101883WikidataQ60488410 ScholiaQ60488410MaRDI QIDQ2437758FDOQ2437758

Nicolas Nisse, F. Giroire, Fedor V. Fomin, Dorian Mazauric, Alain Jean-Marie

Publication date: 13 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.01.009

Recommendations

• Catch them if you can
• The slow server problem for uninformed customers
• scientific article; zbMATH DE number 2086489
• scientific article; zbMATH DE number 1830746
• Time to market and impatient customers
• Zipf's law for web surfers

zbMATH Keywords

interval graphscops and robber gamesPSPACE-completeprefetching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Applications of game theory (91A80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Games involving graphs (91A43) Internet topics (68M11)

Cites Work

• Cops and robbers in graphs with large girth and Cayley graphs
• Vertex-to-vertex pursuit in a graph
• Cops and robbers in a random graph
• Relationships between nondeterministic and deterministic tape complexities
• A game of cops and robbers
• An annotated bibliography on guaranteed graph searching
• Cop and Robber Games When the Robber Can Hide and Ride
• Pursuing a fast robber on a graph
• Cops and robbers from a distance
• Searching and sweeping graphs: a brief survey
• On the computational complexity of a game of cops and robbers
• Tight bounds for eternal dominating sets in graphs
• Guard Games on Graphs: Keep the Intruder Out!
• The complexity of pursuit on a graph
• Lower Bounds for the Cop Number when the Robber is Fast
• On a pursuit game played on graphs for which a minor is excluded
• Title not available (Why is that?)
• How to Guard a Graph?
• On a generalization of Meyniel's conjecture on the Cops and Robbers game
• Cops and robber game without recharging
• Parameterized algorithm for eternal vertex cover

Cited In (8)

• Study of a combinatorial game in graphs through linear programming
• Complexity of the game domination problem
• Eternally dominating large grids
• Maximum rooted connected expansion
• A connected version of the graph coloring game
• Connected surveillance game
• Title not available (Why is that?)
• Catch them if you can

This page was built for publication: To satisfy impatient web surfers is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437758)