Computing role assignments of chordal graphs

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

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

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 complexitygraph homomorphismchordal graphrole assignment

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (10)

Edge homogeneous colorings ⋮ Computing role assignments of split graphs ⋮ Parameterizing role coloring on forests ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ On the complexity of role colouring planar graphs, trees and cographs ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Role colouring graphs in hereditary classes ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications ⋮ Role coloring bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A complete complexity classification of the role assignment problem
• Counting the number of independent sets in chordal graphs
• Finite planar emulators for \(K_{4,5} - 4K_{2}\) and \(K_{1,2,2,2}\) and Fellows' conjecture
• Comparing universal covers in polynomial time
• Finite common coverings of pairs of regular graphs
• Role colouring a graph
• Covering regular graphs
• 2-role assignments on triangulated graphs.
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• How hard is it to determine if a graph has a 2-role assignment?
• Power of Natural Semijoins
• Constructing 5-Arc-Transitive Cubic Graphs
• Partial covers of graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• The role assignment model nearly fits most social networks
• Fixed-parameter complexity of \(\lambda\)-labelings

This page was built for publication: Computing role assignments of chordal graphs