Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Computing role assignments of chordal graphs.

Hof, P van 't and Paulusma, Daniel and Rooij, J.M.M. van (2010) 'Computing role assignments of chordal graphs.', Theoretical computer science., 411 (40-42). pp. 3601-3613.

Abstract

In social network theory, a simple graph G is called k-role assignable if there is a surjective mapping that assigns a number from {1,…,k}, called a role, to each vertex of G such that any two vertices with the same role have the same sets of roles assigned to their neighbors. The decision problem whether such a mapping exists is called the k-Role Assignment problem. This problem is known to be NP-complete for any fixed k≥2. In this paper, we classify the computational complexity of the k-Role Assignment problem for the class of chordal graphs. We show that for this class the problem can be solved in linear time for k=2, but remains NP-complete for any k≥3. This generalizes earlier results by Sheng and answers her open problem.

Item Type:Article
Keywords:Role assignment, Graph homomorphism, Chordal graph, Computational complexity.
Full text:PDF - Accepted Version (478Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.tcs.2010.05.041
Publisher statement:NOTICE: this is the author's version of a work that was accepted for publication in Theoretical computer science.
Record Created:06 Oct 2010 12:50
Last Modified:03 Apr 2013 13:17

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library