The p-median problem with mutual communication is defined as follows: Let G=(V,E) be an undirected graph with positive edge lengths. Suppose that each node represents an existing facility. The objective is to locate p new facilities (medians) while minimizing the sum of weighted distances between all pairs of new facilities and pairs of new existing facilities. The paper presents new complexity results for this model and for some of its variants.
