Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

The computational complexity of the role assignment problem

Share/Save/Bookmark

Fiala, J. and Paulusma, D. (2003) The computational complexity of the role assignment problem. [Report]

[img]
Preview
PDF
219Kb
Abstract:A graph $G$ is $R$-role assignable if there is a locally surjective homomorphism from $G$ to $R$, i.e. a vertex mapping $r:V_G\to V_R$, such that the neighborhood relation is preserved: $r(N_G(u)) = N_R(r(u))$. Kristiansen and Telle conjectured that the decision problem whether such a mapping exists is an {\sf NP}-complete problem for any connected graph $R$ on at least three vertices. In this paper we prove the conjecture and show further corollaries for disconnected graphs and related problems.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65854
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 213722