An alternative proof for the equivalence of ∞-searcher and 2-searcher
| Autor: | Masafumi Yamashita, Tsunehiko Kameda, Ichiro Suzuki |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
0209 industrial biotechnology
Conjecture General Computer Science 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics 020901 industrial engineering & automation Light source 010201 computation theory & mathematics Calculus Equivalence (formal languages) Mathematics |
| Zdroj: | Theoretical Computer Science. 634:108-119 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2016.04.016 |
| Popis: | It was conjectured in 1992 that the 2-searcher, who has two flashlights, has the same searching capability as the ∞-searcher, who has an omni-directional light source. Park et al. proved this conjecture affirmatively in 2001, but their proof is rather complicated and not easy to understand. In this paper we present an alternative proof, which we believe is conceptually more transparent and easier to understand. For this purpose, we introduce a tool called the 2-link visibility diagram that represents 2-link visibility, which has other applications. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect