Sensor Location Problem for a Multigraph

Abstract

We introduce sparse linear underdetermined systems with embedded network structure. Their structure is inherited from the non-homogeneous network flow programming problems with nodes of variable intensities. One of the new applications of the researched underdetermined systems is the sensor location problem (SLP) for a multigraph. That is the location of the minimum number of sensors in the nodes of the multigraph, in order to determine the arcs flow volume and variable intensities of nodes for the whole multigraph. Research of the rank of the sparse matrix is based on the constructive theory of decomposition of sparse linear underdetermined systems.