International Journal of Mathematics and Mathematical Sciences
Volume 2005 (2005), Issue 9, Pages 1405-1413
An efficient -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.
In 1998, Pandu Rangan et al. Proved that
locating the -centroid for an arbitrary graph is
-hard by reducing the problem of finding the maximum
clique size of a graph to the -centroid location problem. They
have also given an efficient polynomial time algorithm for
locating the -centroid for maximal outerplanar graphs,
Ptolemaic graphs, and split graphs. In this paper, we present an
time algorithm for locating the -centroid for
cographs, where is the number of vertices and is the
number of edges of the graph.