Computing role assignments of split graphs

DOI10.1016/j.tcs.2016.05.011zbMath1339.05384MaRDI QIDQ287443

Mitre C. Dourado

Publication date: 26 May 2016

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

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

zbMATH Keywords

NP-complete problems; social networks; graph algorithms; split graphs; role assignments

Mathematics Subject Classification ID

91D30: Social networks; opinion dynamics

05C82: Small world graphs, complex networks (graph-theoretic aspects)

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

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

An algorithmic framework for locally constrained homomorphisms, Parameterizing role coloring on forests, On the number of maximal independent sets in minimum colorings of split graphs, Role colouring graphs in hereditary classes, Role coloring bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing role assignments of proper interval graphs in polynomial time
• Computing role assignments of chordal graphs
• Dominating sets for split and bipartite graphs
• A complete complexity classification of the role assignment problem
• Comparing universal covers in polynomial time
• Clustering and domination in perfect graphs
• The splittance of a graph
• Role colouring a graph
• Some simplified NP-complete graph problems
• 2-role assignments on triangulated graphs.
• Algorithmic graph theory and perfect graphs
• HAMILTONian circuits in chordal bipartite graphs
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• How hard is it to determine if a graph has a 2-role assignment?
• Graph Transformations
• The role assignment model nearly fits most social networks