P. van 't Hof
Computing role assignments of chordal graphs
Hof, P. van 't; Paulusma, D.; Rooij, J.M.M. van
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
A new characterization of P6-free graphs
(2008)
Conference Proceeding
Finding Induced Paths of Given Parity in Claw-Free Graphs
(2009)
Conference Proceeding
Partitioning graphs into connected parts
(2009)
Journal Article
Partitioning graphs into connected parts
(2009)
Conference Proceeding
A new characterization of P6-free graphs
(2010)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search