About CS&CE
Prospective Students
Research
Staff
Dept Comp Sci & Comp Eng
Contact Details
La Trobe University
Victoria 3086
AUSTRALIA
Tel: +61 3 9479 1107
Fax: +61 3 9479 3060
Email: info
@cs.latrobe.edu.au
|
 |
Research Publications - Abstract
Department of Computer Science & Computer Engineering
|
Veeraraghavan, P. |
| Publication Year: |
2009 |
| Paper Title: |
An improved g-centroid location algorithm for Ptolemaic graphs |
| Journal Name: |
International Journal of Multimedia and Ubiquitous Engineering |
| Volume: |
4/2 |
| Pages: |
91 - 98 |
| Abstract: |
We have presented an O(m²) time algorithm for lcation 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 . 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 unders consideration will be dense (i.e. m ≈ O(n²)) and the algoithm presented will output g-centroid in O(n4) time. In this paper, we present and efficient (O(n³) time algoirithm to locate the g-entroid for dense Ptolemaic graphs.
|
|
|
