Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond

DOI10.1007/978-3-319-25258-2_24zbMath1471.91060OpenAlexW2295446126MaRDI QIDQ3460727

Jara Uitto, Roger Wattenhofer, Klaus-Tycho Foerster, Rijad Nuridini

Publication date: 8 January 2016

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-25258-2_24

Mathematics Subject Classification ID

Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Positional games (pursuit and evasion, etc.) (91A24)

Related Items (5)

Collaboration Without Communication: Evacuating Two Robots from a Disk ⋮ A tight lower bound for the capture time of the cops and robbers game ⋮ Bounds on the length of a game of cops and robbers ⋮ Wireless evacuation on \(m\) rays with \(k\) searchers ⋮ Two-agent tree evacuation

Cites Work

• Characterizations of \(k\)-copwin graphs
• The capture time of grids
• A game of cops and robbers
• Cop-win graphs with maximum capture-time
• The capture time of a graph
• Cops and robbers in graphs with large girth and Cayley graphs
• On the cop number of a graph
• Vertex-to-vertex pursuit in a graph
• The capture time of the hypercube
• Cops and robbers is EXPTIME-complete
• On the diameter of a graph
• Variations on cops and robbers
• On Meyniel's conjecture of the cop number
• k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth
• A Bound for the Cops and Robbers Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond