An efficient g -centroid location algorithm for cographs

V. Prakash

International Journal of Mathematics and Mathematical Sciences, 2005, vol. 2005, 1-9

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 ( n m ) 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.

Date: 2005
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/IJMMS/2005/858629.pdf (application/pdf)
http://downloads.hindawi.com/journals/IJMMS/2005/858629.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jijmms:858629

DOI: 10.1155/IJMMS.2005.1405

Access Statistics for this article

More articles in International Journal of Mathematics and Mathematical Sciences from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().