Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem

Monitoring flows on networks is a research area for which a number of applications are waiting for models and algorithms to face new problems emerging with a very high paced. In this paper we analyze a particular optimization problem, namely the Dominating Paths Problem (DPP), that has application in this field especially for urban transportation networks. Given an undirected graph G = (V, E) and a subset B subset of V of bound vertices, we look for a set of vertices M of minimum size such that each element of M is the origin of one or more paths, and, the set of all these paths dominates B. For this NP-hard problem, we present an approximation algorithm and new heuristic procedures extensively evaluated on a set of test instances. We defined two different sets of benchmarks: grid graphs and random graphs. Moreover, we included two test cases taken from real traffic networks. Computational results, discussed in the paper, give insights both on the problem and on algorithms' performance. (c) 2004 Published by Elsevier Ltd.