Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334291 | Theoretical Computer Science | 2005 | 15 Pages |
Abstract
If such a mapping exists the graph G is called R-role assignable and the corresponding decision problem is called the R-role assignment problem. Kristiansen and Telle conjectured that the R-role assignment problem is an NP-complete problem for any simple connected graph R on at least three vertices. In this paper we prove their conjecture. In addition, we determine the computational complexity of the role assignment problem for nonsimple and disconnected role graphs, as these are considered in social network theory as well.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
JiÅÃ Fiala, Daniël Paulusma,