The generic problem studied is to locate p distinguishable facilities on a tree to satisfy upper-bound constraints on distances between pairs of facilities, given that each facility must be located within its own feasible region, which is defined as a subtree of the tree. We present a parallel location scheme (PLS) for solving the problem that can be implemented as an NC-algorithm. We also introduce parallel NC-algorithms based on the PLS for the minimax versions of the problem, including the distance-constrained p-center problem with mutual communication. Combining the PLS and the improved Megiddo's parametric technique, we develop strongly polynomial serial algorithms for the minimax problems; the algorithms have the best complexities currently available in the literature. Efficient parallel algorithms are given for obtaining optimal regions of the facilities.
