Computing role assignments of chordal graphs

DOI10.1016/j.tcs.2010.05.041zbMath1231.05182MaRDI QIDQ708211

Daniël Paulusma, Johan M. M. van Rooij, Pim van 't Hof

Publication date: 11 October 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.05.041

zbMATH Keywords

computational complexity; graph homomorphism; chordal graph; role assignment

Mathematics Subject Classification ID

91D30: Social networks; opinion dynamics

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)