earticle

영어

We have presented an 2()Om 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. =()mOn) 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. 2()mOn) and the algorithm presented will output g-centroid in 4()On time. In this paper, we present an efficient 3()On time algorithm to locate the g-centroid for dense Ptolemaic graphs.