含回路网络的中心选址 Ⅰ.单回路情形

本文对单回路网络引入了一种新的双标号准则,借此给出了求其1-中心的O(n)阶算法。对边不交的多回路网络,在Ⅱ中将给出一个有效的去边准则。设网络G=(V,E)是一个无向连通图,V(G)和E(E)分别表示其顶点集和边集。在此,我们考虑如下的网络选址问题其中p∈G表示p也可取在边上。关于树网络的中心选址,有关文献[3]、[4]、[5]已做了深入的研究。本文对单回路网络引进了双标号准则,从而给出此类网络1-中心选址的O(n)阶算法。