Dispersing facilities on a network

The p-maxisum dispersion problem consists of locationg p facilities at vertices of a network in order to maximize the sum of the distances between all pairs of them. The decision version of this probem is shown to be strongly NP-complete. For a tree network a solution algorithm with a complexity linear in the number of vertices is proposed for fixed p. Moreover, the p-maxisum dispersion probelm on a general network is shown to be a particular case of the quadratic knapsack problem, for which fairly efficient algorithms are available.