오프라인 경찰수에 대한 밀착상한: 경찰이 도둑보다 빠른 경우 (The Tight Upper Bound on the Offline Cop Number: In the Case Where the Cops Are Fast)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 시스템 및 이론 / 40권 / 4호 / 193 ~ 200페이지
· 저자명 : 나현숙, 조유석

초록

지정된 경로를 따라 격자 그래프를 탐색하는 경찰들이 있다. 도둑은 이들의 경로를 미리 모두 알고 있지만, 경찰은 도둑의 위치에 대해 전혀 알지도 못하고, 경로를 수정할 수도 없다. 그러면 유한한 시간 내에 도둑을 잡기 위해서는 몇 명의 경찰이 필요할까? 이 숫자, 즉 도둑을 잡기위해 필요한 최소의 경찰수를 오프라인 경찰수 라고 한다. 오프라인 경찰수에 대해 알려진 자명한 상한은 인데, 왜냐하면 명의 경찰이 일렬횡대로 서서 격자그래프를 바닥부터 천장까지 탐색해간다면 도둑은 어떻게 해도 시간 내에 잡힐 수밖에 없기 때문이다. Brass et al. [1]은 교번모델 - 매시간 먼저 경찰이 최대 개의 간선을 이동한 후 도둑이 최대 한 개의 간선을 이동하는 모델 - 에 대해서, 도둑은 언제나명의 경찰을 피할 수 있으며, 명의 경찰이 어떠한 도둑도 잡을 수 있도록 하는 탐색경로를 제시했다. 즉, 오프라인 경찰수의 하한이 이고 상한이 임을 증명했다. 또한 인 경우, 명의 경찰이 도둑을 잡는 탐색경로를 제시함으로써, 인 교번모델의 오프라인 경찰수가 임을 보였다. 이 논문에서는 나머지 경우, 즉 인 교번모델에서, 명의 경찰이 어떠한 도둑도 잡을 수 있도록 하는 탐색경로를 제시하여 오프라인 경찰수가 임을 보인다.

영어초록

Imagine that cops patrol the grid on fixed routes. The robber has full knowledge of the cops' routes in advance, but the cops know nothing of the robber's position and cannot change their routes. Then how many cops are necessary to catch the robber in finite time? This number, the minimum number of cops needed to catch the robber is called the offline cop number. A trivial upper bound is since cops standing abreast and sweeping the grid from the bottom to the top will catch any smartest robber within time in spite of knowing nothing of the robber's position. In an alternating-move-model where at each time the cops first move (at most) edges at a time and then the robber moves at most one edge, Brass et al. [1] proved a lower bound of and an upper bound of ; they showed that a robber can always escape detection ofcops indefinitely and provided a strategy for cops to catch the robber. They closed the gap in the case where , by giving a strategy for cops to catch the robber. In this note, we close the gap for the other case where by presenting a strategy for cops to catch the robber.

참고자료

· 없음