Top

Published in:

2016 | OriginalPaper | Chapter

On the Capture Time of Cops and Robbers Game on a Planar Graph

Authors : Photchchara Pisantechakool, Xuehou Tan

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper examines the capture time of a planar graph in a pursuit-evasion games’ variant called the cops and robbers game. Since any planar graph requires at most three cops, we study the capture time of a planar graph G of n vertices using three cops, which is denoted by \(capt_3(G)\). We present a new capture strategy and show that \(capt_3(G) \le 2n\). This is the first result on \(capt_3(G)\).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter The Mixed Evacuation Problem

Aigner, M., Fromme, M.: A game of cops and robbers. Discrete Appl. Math. 8(1), 1–12 (1984)MathSciNetCrossRefMATH

Alspach, B.: Searching and sweeping graphs: a brief survey. Le Mathematiche 59, 2 (2004)MathSciNetMATH

Bhaduaria, D., Klein, K., Isler, V., Suri, S.: Capturing an evader in polygonal environments with obstacles: the full visibility case. Int. J. Robot. Res. 31(10), 1176–1189 (2012)CrossRef

Bienstock, D., Seymour, P.: Monotonicity in graph searching. J. Algorithm 12, 239–245 (2011)MathSciNetCrossRefMATH

Bonato, A., Golovach, P., Hahn, G., Kratochvíl, J.: The capture time of a graph. Discrete Math. 309, 5588–5595 (2009)MathSciNetCrossRefMATH

Gal, I.: Search Games. Addison-Wesley, Reading (1982)MATH

Kehagias, A., Hollinger, G.A., Singh, S.: A graph search algorithm for indoor pursuit-evasion. Math. Comput. Model. 50(9–10), 1305–1317 (2008)MathSciNetMATH

LaPaugh, A.S.: Recontamination does not help to search a graph. J. ACM 40, 224–245 (1993)MathSciNetCrossRefMATH

Maurer, A., McCauley, J., Valeva, S.: Cops and robbers on planar graphs. In: Summer 2010 Interdisciplinary Research Experience for Undergraduates. University of Minnesota (2010)

10.

Mehrabian, A.: The capture time of grids. Discrete Math. 311, 102–105 (2011)MathSciNetCrossRefMATH

11.

Nowakowski, R., Winkler, R.P.: Vertex-to-vertex pursuit in a graph. Discrete Math. 43, 235–239 (1983)MathSciNetCrossRefMATH

12.

Parsons, T.D.: Pursuit-evasion in a graph. In: Alavi, Y., Lick, D.R. (eds.) Theory and Applications of Graphs. Lecture Notes in Mathematics, vol. 642, pp. 426–441. Springer, Heidelberg (1978)CrossRef

13.

Parsons, T.D.: The search number of a connected graph. In: Proceedings of 9th South-Eastern Conference on Combinatorics Graph Theory and Computing, pp. 549–554 (1978)

14.

Quilliot, A.: Some results about pursuit games on metric spaces obtained through graph theory techniques. Eur. J. Comb. 7(1), 55–66 (1986)MathSciNetCrossRefMATH

Title: On the Capture Time of Cops and Robbers Game on a Planar Graph
Authors: Photchchara Pisantechakool
Xuehou Tan
Publisher: Springer International Publishing
Book: Combinatorial Optimization and Applications
Print ISBN: 978-3-319-48748-9

Electronic ISBN: 978-3-319-48749-6

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-319-48749-6_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner