To satisfy impatient web surfers is hard

DOI10.1016/J.TCS.2014.01.009MaRDI QIDQ2437758zbMATH OpenOpenAlexDBLPWikidataFDO

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

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

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)

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

Cites work

• scientific article; zbMATH DE number 1665333 (Why is no real title available?)
• A game of cops and robbers
• An annotated bibliography on guaranteed graph searching
• Cop and robber games when the robber can hide and ride
• Cops and robber game without recharging
• Cops and robbers from a distance
• Cops and robbers in a random graph
• Cops and robbers in graphs with large girth and Cayley graphs
• Guard games on graphs: keep the intruder out!
• How to Guard a Graph?
• Lower bounds for the cop number when the robber is fast
• On a generalization of Meyniel's conjecture on the Cops and Robbers game
• On a pursuit game played on graphs for which a minor is excluded
• On the computational complexity of a game of cops and robbers
• Parameterized algorithm for eternal vertex cover
• Pursuing a fast robber on a graph
• Relationships between nondeterministic and deterministic tape complexities
• Searching and sweeping graphs: a brief survey
• The complexity of pursuit on a graph
• Tight bounds for eternal dominating sets in graphs
• Vertex-to-vertex pursuit in a graph

Cited in

(9)

• Study of a combinatorial game in graphs through linear programming
• Study of a combinatorial game in graphs through linear programming
• Complexity of the game domination problem
• Maximum rooted connected expansion
• Connected surveillance game
• Maximum rooted connected expansion
• A connected version of the graph coloring game
• Connected surveillance game
• 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)