Multiple cover problem on undirected flow networks

Problems concerning the optimum location of various devices installed in tr ansport, communication, and other types of networks relate to the so-called location on network problems. In this paper, we show how an expanded multi ple cover problem can be solved in polynomial time for the case of an undir ected flow network, which is a special case of the location problem on flow networks. Up to now, such problems were solved in polynomial time for cond itions when values of the flow to each vertex were set above a certain cons tant magnitude. Here, we show the possibility of solving these problems by a simple algorithm even in cases where these magnitudes are different for e ach vertex. (C) 2000 Scripts Technica.