Computing role assignments of chordal graphs
DOI10.1016/J.TCS.2010.05.041zbMATH Open1231.05182OpenAlexW2073528847MaRDI QIDQ708211FDOQ708211
Authors: Pim Van 't Hof, Daniël Paulusma, Johan M. M. Van Rooij 
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
Recommendations
Social networks; opinion dynamics (91D30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Title not available (Why is that?)
- Role colouring a graph
- 2-role assignments on triangulated graphs.
- How hard is it to determine if a graph has a 2-role assignment?
- Local computations in graphs: the case of cellular edge local computations
- 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
- A complete complexity classification of the role assignment problem
- Comparing universal covers in polynomial time
- Title not available (Why is that?)
- Power of Natural Semijoins
- Fixed-parameter complexity of \(\lambda\)-labelings
- Title not available (Why is that?)
- Covering regular graphs
- Partial covers of graphs
- 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
- Finite common coverings of pairs of regular graphs
- Constructing 5-Arc-Transitive Cubic Graphs
Cited In (21)
- Graph classes with structured neighborhoods and algorithmic applications
- Parameterizing role coloring on forests
- On the complexity of role colouring planar graphs, trees and cographs
- Computing some role assignments of Cartesian product of graphs
- The complexity of surjective homomorphism problems-a survey
- Computing role assignments of proper interval graphs in polynomial time
- An algorithmic framework for locally constrained homomorphisms
- Title not available (Why is that?)
- Computing role assignments of split graphs
- Computing role assignments of Cartesian product of graphs
- Computing role assignments of proper interval graphs in polynomial time
- Role coloring bipartite graphs
- Title not available (Why is that?)
- A complete complexity classification of the role assignment problem
- Graph classes with structured neighborhoods and algorithmic applications
- Role colouring graphs in hereditary classes
- 2-role assignments on triangulated graphs.
- An algorithmic framework for locally constrained homomorphisms
- Computing Role Assignments of Chordal Graphs
- How hard is it to determine if a graph has a 2-role assignment?
- Edge homogeneous colorings
This page was built for publication: Computing role assignments of chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q708211)
