A model solution for radar surveillance problem / Nasaruddin Zenon and Rosmah Ali

This paper is a result of a problem posed by Professor L. H. Harper2 to the Combinatorial Theory class in spring 1985. The problem is as follows Given M radar sites with the ith site having antennae and N moving space objects, is it possible to monitor the jth objects β different sites taking into account that the jth object may not be always visible from site I ? If so find such an assignment. The authors' previous approach to this problem was to view it as a reduced network flow problem. This reduction was possible because the network was regular3. The model was tested with concrete data using Ford and Fulkerson Algorithm and Dinic Algorithm (Please refer to [I] and [2] for the details of these algorithms.). In this paper we will give a generalized newtwork flow (GNF) formulation to the problem and we will illustrate the technique involved in solving a multipl esources and multiple-sinks maximum flow problem with special underlying structures. In the latter part of the paper we will give an insight as to how this problem can be further reduced using the technique of network synthesis.