Fine-grained Lower Bounds on Cops and Robbers
From MaRDI portal
Publication:5009566
DOI10.4230/LIPIcs.ESA.2018.9OpenAlexW2888061026MaRDI QIDQ5009566
Jara Uitto, Seth Pettie, Sebastian F. Brandt
Publication date: 4 August 2021
Full work available at URL: https://dblp.uni-trier.de/db/conf/esa/esa2018.html#BrandtPU18
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Characterizations of \(k\)-copwin graphs
- The complexity of pursuit on a graph
- Bounds on the length of a game of cops and robbers
- Sur la trialité et certains groupes qui s'en déduisent
- A game of cops and robbers
- Cops and robbers in graphs with large girth and Cayley graphs
- Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
- On the cop number of a graph
- Which problems have strongly exponential complexity?
- On the computational complexity of a game of cops and robbers
- Cops and robbers is EXPTIME-complete
- Pursuing a fast robber on a graph
- On Meyniel's conjecture of the cop number
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- A Bound for the Cops and Robbers Problem
- Über ein Problem von K. Zarankiewicz
- Some combinatorial game problems require Ω( n k ) time
- Provably Difficult Combinatorial Games
- Classes of Pebble Games and Complete Problems
- A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
- Pursuit and evasion from a distance: algorithms and bounds
- Fast approximation algorithms for the diameter and radius of sparse graphs
- On Graphs that do not Contain a Thomsen Graph
- The NP-completeness column: An ongoing guide
