期刊名称：International Journal of Mathematics and Mathematical Sciences
印刷版ISSN：0161-1712
电子版ISSN：1687-0425
出版年度：2005
卷号：2005
DOI：10.1155/IJMMS.2005.1405
出版社：Hindawi Publishing Corporation
摘要：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.
