To satisfy impatient web surfers is hard

DOI10.1016/j.tcs.2014.01.009zbMath1282.68082DBLPjournals/tcs/FominGJMN14OpenAlexW2084101883WikidataQ60488410 ScholiaQ60488410MaRDI QIDQ2437758

Nicolas Nisse, Fedor V. Fomin, Alain Jean-Marie, Frederic 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

prefetchinginterval graphsPSPACE-completecops and robber games

Mathematics Subject Classification ID

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

Related Items (7)

Complexity of the game domination problem ⋮ A connected version of the graph coloring game ⋮ Study of a combinatorial game in graphs through linear programming ⋮ Maximum rooted connected expansion ⋮ Unnamed Item ⋮ Eternally dominating large grids ⋮ Connected surveillance game

Cites Work

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

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