One-visibility cops and robber on trees
| Autor: | Boting Yang, Tanzina Akter |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
021103 operations research
General Computer Science Visibility (geometry) 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Variation (game tree) Software_PROGRAMMINGTECHNIQUES 16. Peace & justice 01 natural sciences Upper and lower bounds Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Mathematics |
| Zdroj: | Theoretical Computer Science. 886:139-156 |
| ISSN: | 0304-3975 |
| Popis: | The one-visibility cops and robber game is a variation of the classic cops and robber game, where one-visibility means that the information of the robber is known to all cops only when the distance between the robber and at least one cop is at most one. In this paper, we give a lower bound on the one-visibility copnumber of general trees. We present strategies to clear trees according to their structures. We propose a linear-time algorithm for computing the one-visibility copnumber of trees. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect