International Journal of Mathematics and Mathematical Sciences
Volume 2005 (2005), Issue 9, Pages 1405-1413
doi:10.1155/IJMMS.2005.1405
An efficient g-centroid location algorithm for cographs
Department of Computer Science and Computer Engineering, La Trobe University Bundoora, Melbourne 3086, VIC, Australia
Received 19 August 2004; Revised 17 January 2005
Copyright © 2005 V. Prakash. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
In 1998, Pandu Rangan et al. Proved that
locating the g-centroid for an arbitrary graph is
𝒩𝒫-hard by reducing the problem of finding the maximum
clique size of a graph to the g-centroid location problem. They
have also given an efficient polynomial time algorithm for
locating the g-centroid for maximal outerplanar graphs,
Ptolemaic graphs, and split graphs. In this paper, we present an
O(nm) time algorithm for locating the g-centroid for
cographs, where n is the number of vertices and m is the
number of edges of the graph.