受限p-中心的并行迭代算法

提出了受限 p-中心的多项式时间并行迭代算法 ,分析了这些算法的计算复杂性 .计算实例表明所提出的算法简洁有效 .本文的算法还可以对其它关于受限 p-中心及 p-中心的启发式算法和近似算法进行补充 ,以此为基础容易获得相应的 Tabu Search算法和遗传算法 .

A Parallel Iterative Algorithm for Constrained p-Centers

The constrained \$p\|\$center problem, proposed by setting emergent service facilities such as police stations and fire stations, is defined as to find \$p\$ vertices in the subset \$D\$ of \$V\$ in order to serve the subset \$R\$ of \$V\$ by minimizing the maximum serving distance in an edge\|weighted graph \$G=(V, E)\$. This paper presents some algorithms and a parallel iterative algorithm to solve constrained \$p\|\$center in polynomial time. We investigate the complexities of these algorithms, which are proved to be very effective in our computing experiences. These algorithms can also be embedded in any heuristic or approximate algorithm for constrained \$p\|\$center and \$p\|\$center. Based these algorithms, the corresponding tabu search and genetic algorithms can be easily designed.