Technical Note—A Polynomial Algorithm for the Equal Capacity p-Center Problem on Trees

Publisher Website
Google Scholar
Abstract
The uncapacitated p-center problem has been shown to be NP-Hard for the case of a general network, yet polynomial algorithms exist for the case of a tree network. We extend the results for trees to include the case where each center can serve a limited number of customers and show that the capacitated p-center problem on trees can be solved in polynomial time when the capacities are identical. The algorithm consists of solving a capacitated covering problem and then using search routines to find the optimal domination radius. We show that the addition of center capacities to either the vertex center problem or the absolute center problem requires a multiplicative factor of O(n) more work, relative to that required for the uncapacitated problems, to solve the related covering problems (n is the number of vertices in the tree).

This publication has 0 references indexed in Scilit: