1B2 The Multicover Problem in Graphs arising from Patrol Route Planning

概要

論文の詳細を見る
In this paper, we consider the following covering problem in graphs which is motivated by patrol route planning. Suppose that we are given a graph G=(V,E), a cost function c:2^E→R_+ and a requirement function r:V→Z_+, where R_+ and Z_+ represent the set of nonnegative reals and integers, respectively. Then, we consider the problem of finding minimum cost k subgraphs with a prescribed property (e.g., trees or paths) such that each v∈V is contained in at least r(v) subgraphs, where the cost of each subgraph is defined by the value of the function c for its edge set and the cost of k subgraphs is defined by the sum of their costs. Since this problem includes the travelling salesman problem as a subcase, it is NP-hard. In this paper, we consider two special cases of this problem. We first consider the problem where we cover the input graph by using trees. For this problem, we present a heuristic algorithm and we apply our algorithm to a numerical example arising from Nagoya City in Japan. We next consider the problem where we are given a path as the input graph and we cover it by using subpaths. For this problem, we first show that if each edge is given a cost and the cost of each path is defined by the sum of the costs of the edges contained in it, this problem can be solved in time bounded by a polynomial in the size of G, k and max{r(v)|v∈V}. Next, we show that if k=max{r(v)|v∈V}holds, this problem can be solved in polynomial time for a general cost function. Furthermore, we prove that if each edge is given a cost and the cost of each path is defined by the square of the sum of the costs of the edges contained in it, we can solve this problem more efficiently.
一般社団法人日本機械学会の論文
2009-07-04

1B2 The Multicover Problem in Graphs arising from Patrol Route Planning

スポンサーリンク

概要

著者

関連論文

スポンサーリンク