An efficientg-centroid location algorithm for cographs Academic Article uri icon


  • In 1998, Pandu Rangan et al. Proved that locating theg-centroid for an arbitrary graph is-hard by reducing the problem of finding the maximum clique size of a graph to theg-centroid location problem. They have also given an efficient polynomial time algorithm for locating theg-centroid for maximal outerplanar graphs, Ptolemaic graphs, and split graphs. In this paper, we present anO(nm)time algorithm for locating theg-centroid for cographs, wherenis the number of vertices andmis the number of edges of the graph.

publication date

  • 2005