Computing role assignments of chordal graphs

详细信息    查看全文

• 作者：Pim van &#x2019 ; t Hof ; Danië ; l Paulusma ; Johan M.M. van Rooij
• 关键词：Role assignment ; Graph homomorphism ; Chordal graph ; Computational complexity
• 刊名：Theoretical Computer Science
• 出版年：2010
• 出版时间：6 September 2010
• 年：2010
• 卷：411
• 期：40-42
• 页码：3601-3613
• 全文大小：474 K

文摘

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.