We suggest a uniform game-theoretic approach to "width" graph parameters. We consider a search problem on a graph in which one cop in a helicopter flying from vertex to vertex tries to catch the robber. The existence of the winning program for the cop in this problem depends only on the robber's speed. We investigate the problem of finding the minimal robber's speed which prevents the cop from winning. We examine two cases of the problem. In the first one the cop can visit each vertex of a graph only once. In the second case the cop cannot afford "recontamination" of vertices. We show that in the first case the problem of finding the minimal robber's speed is equivalent to the bandwidth minimization problem. In the second case we show that the problem is equivalent to the natural generalization of the bandwidth problem and is closely approximated by the pathwidth. Also we show that the problem of computing the minimal robber's speed is NP-hard in both cases. (C) 1998 Elsevier Science B.V. All rights reserved. [References: 28]
展开▼
