Fast searching games on graphs |
| |
| Authors: | Donald Stanley Boting Yang |
| |
| Institution: | (1) Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands;(2) Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Campus Nord–C6. E-08034, Barcelona, Spain |
| |
| Abstract: | Given a graph, suppose that intruders hide on vertices or along edges of the graph. The fast searching problem is to find
the minimum number of searchers required to capture all the intruders satisfying the constraint that every edge is traversed
exactly once and searchers are not allowed to jump. In this paper, we prove lower bounds on the fast search number. We present
a linear time algorithm to compute the fast search number of Halin graphs and their extensions. We present a quadratic time
algorithm to compute the fast search number of cubic graphs. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
