Locating facilities which interact: Some solvable cases (Q689235)

The problem is to find the location of new facilities on a transport network with \(n\) nodes such that the sum of the cost of interaction between the new facilities and \(n\) existing facilities on the network and the cost of interaction between pairs of new facilities is minimized. The authors give a polynomial time algorithm for problems in which the interaction costs are general functions of network distances. More precisely, the considered problem is seen to be equivalent to a node selection problem and the algorithm is given for the case when the flow graph is Halin. Generalized Halin graphs are also considered.