An efficient \(g\)-centroid location algorithm for cographs (Q2575946)

Summary: In 1998, \textit{C. Pandu Rangan} et al. [Ars Comb. 50, 267--278 (1998; Zbl 0963.05044)] proved that locating the \(g\)-centroid for an arbitrary graph is \(\mathcal{NP}\)-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.