Combinatorial aspects of the sensor location problem

Combinatorial aspects of the sensor location problem

0.00 Avg rating0 Votes
Article ID: iaor20071108
Country: Netherlands
Volume: 144
Issue: 1
Start Page Number: 201
End Page Number: 234
Publication Date: Apr 2006
Journal: Annals of Operations Research
Authors: , ,
Keywords: networks: flow, measurement
Abstract:

In this paper we address the Sensor Location Problem, that is the location of the minimum number of counting sensors, on the nodes of a network, in order to determine the arc flow volume of all the network. Despite the relevance of the problem from a practical point of view, there are very few contributions in the literature and no combinatorial analysis is performed to take into account particular structure of the network. We prove the problem is NP-complete in different cases. We analyze special classes of graphs that are particularly interesting from an application point of view, for which we give low order polynomial solution algorithms.

Reviews

Required fields are marked *. Your email address will not be published.