期刊名称：International Journal of Multimedia and Ubiquitous Engineering
印刷版ISSN：1975-0080
出版年度：2009
卷号：4
期号：2
出版社：SERSC
摘要：We have presented an O(m2) time algorithm for locating the g-centroid for Ptolemaic graphs, where n is the number of edges and m is the number of vertices of the graph under consideration [6]. If the graph is sparse (i.e. m=O(n)) then the algorithm presented will output the g-centroid in quadratic time. However, for several practical applications, the graph under consideration will be dense (i.e. mO(n2)) and the algorithm presented will output gcentroid in O(n4) time. In this paper, we present an efficient O(n3) time algorithm to locate the g-centroid for dense Ptolemaic graphs.
