Computing role assignments of split graphs
From MaRDI portal
Publication:287443
DOI10.1016/j.tcs.2016.05.011zbMath1339.05384MaRDI QIDQ287443
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
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