Title :
An Efficient g-Centroid Location Algorithm for Ptolemaic Graphs
Author :
Veeraraghavan, Prakash
Author_Institution :
Dept. of Comput. Sci. & Comput. Eng., La Trobe Univ., Melbourne, VIC
Abstract :
In an earlier paper by C.Pandu et al (1998), we presented an O(m2) algorithm for locating the g-centroid for ptolemaic graphs. Here we improve the time complexity and propose an efficient O(n3)-time algorithm for locating the g-centroid for ptolemaic graphs. This is by defining an auxiliary graph.
Keywords :
computational complexity; graph theory; auxiliary graph; g-centroid location algorithm; ptolemaic graph; time complexity; Application software; Bonding; Computer architecture; Computer science; Distributed computing; Hypercubes; Mobile ad hoc networks; Parallel processing; Telephony; Topology; g-centroid; g-convexity; ptolemaic graphs;
Conference_Titel :
Computer Science and its Applications, 2008. CSA '08. International Symposium on
Conference_Location :
Hobart, ACT
Print_ISBN :
978-0-7695-3428-2
DOI :
10.1109/CSA.2008.49
