Skip to main content

Research Repository

Advanced Search

Computing role assignments of chordal graphs

Hof, P. van 't; Paulusma, D.; Rooij, J.M.M. van

Authors

P. van 't Hof

J.M.M. van Rooij



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 becomes polynomially solvable for k = 2, but remains NP-complete for any k ≥ 3. This generalizes results of Sheng and answers his open problem.

Citation

Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2009). Computing role assignments of chordal graphs. In Fundamentals of computation theory : 17th International Symposium, FCT 2009, Wrocław, Poland, September 2-4, 2009. Proceedings (193-204). https://doi.org/10.1007/978-3-642-03409-1_18

Conference Name 17th International Symposium on Fundamentals of Computation Theory (FCT 2009)
Conference Location Wroclaw, Poland
Start Date Sep 2, 2009
End Date Sep 4, 2009
Publication Date Sep 19, 2009
Deposit Date Oct 15, 2009
Pages 193-204
Series Title Lecture notes in computer science
Series Number 5699
Series ISSN 0302-9743,1611-3349
Book Title Fundamentals of computation theory : 17th International Symposium, FCT 2009, Wrocław, Poland, September 2-4, 2009. Proceedings.
DOI https://doi.org/10.1007/978-3-642-03409-1_18
Public URL https://durham-repository.worktribe.com/output/1160552


You might also like



Downloadable Citations