Show simple item record

dc.contributor.author
Brandt, Sebastian
dc.contributor.author
Emek, Yuval
dc.contributor.author
Uitto, Jara
dc.contributor.author
Wattenhofer, Roger
dc.contributor.editor
Chatzigiannakis, Ioannis
dc.contributor.editor
Indyk, Piotr
dc.contributor.editor
Kuhn, Fabian
dc.contributor.editor
Muscholl, Anca
dc.date.accessioned
2018-02-08T12:32:31Z
dc.date.available
2017-10-06T04:56:13Z
dc.date.available
2018-01-10T15:33:16Z
dc.date.available
2018-02-08T12:32:31Z
dc.date.available
2018-02-01T10:31:12Z
dc.date.available
2018-02-08T12:30:46Z
dc.date.issued
2017
dc.identifier.isbn
978-3-95977-041-5
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPIcs.ICALP.2017.82
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/239572
dc.identifier.doi
10.3929/ethz-b-000192351
dc.description.abstract
For the game of Cops and Robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time, and that there exist graphs in which this capture time is tight. When k >= 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O(n^{k + 1}), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. In this paper, the question of Bonato and Nowakowski is answered on the negative, proving that the O(n^{k + 1}) bound is asymptotically tight for any constant k >= 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.
en_US
dc.format
application/pdf
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
cops and robbers
en_US
dc.subject
capture time
en_US
dc.subject
lower bound
en_US
dc.title
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics
ethz.journal.volume
80
en_US
ethz.journal.abbreviated
Leibniz int. proc. inform.
ethz.pages.start
82
en_US
ethz.size
13 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
en_US
ethz.event.location
Warsaw, Poland
en_US
ethz.event.date
July 10-14, 2017
en_US
ethz.identifier.scopus
ethz.publication.place
Dagstuhl
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09587 - Ghaffari, Mohsen / Ghaffari, Mohsen
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09587 - Ghaffari, Mohsen / Ghaffari, Mohsen
ethz.date.deposited
2017-10-06T04:56:18Z
ethz.source
SCOPUS
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2018-02-08T14:10:43Z
ethz.rosetta.lastUpdated
2020-02-15T11:10:26Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/238013
dc.identifier.olduri
http://hdl.handle.net/20.500.11850/192351
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=A%20Tight%20Lower%20Bound%20for%20the%20Capture%20Time%20of%20the%20Cops%20and%20Robbers%20Game&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics&rft.date=2017&rft.volume=80&rft.spage=82&rft.issn=1868-8969&rft.au=Brandt,%20Sebastian&Emek,%20Yuval&Uitto,%20Jara&Wattenhofer,%20Roger&rft.isbn=978-3-95977-041-5&rft.genre=proceeding&rft_id=info:doi/978-3-95977-041-5&rft.btitle=44th%20International%20Colloquium%20on%20Automata,%20Languages,%20and%20Programming%20(ICALP%202017)
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record