m-Median and m-Center Problems with Mutual Communication: Solvable Special Cases

In this paper, we consider the network version of the m-median problem with mutual communication (MMMC). We reformulate this problem as a graph theoretic node selection problem defined on a special graph. We give a polynomial time algorithm to solve the node selection problem when the flow graph (graph that denotes the interaction between pairs of new facilities in MMMC) has a special structure. We also show that with some modification in the algorithm for MMMC, the m-center problem with mutual communication can also be solved when the flow graph has a special structure.