How hard is it to determine if a graph has a 2-role assignment?
From MaRDI portal
Publication:2714905
DOI<link itemprop=identifier href="https://doi.org/10.1002/1097-0037(200103)37:2<67::AID-NET1>3.0.CO;2-9" /><67::AID-NET1>3.0.CO;2-9 10.1002/1097-0037(200103)37:2<67::AID-NET1>3.0.CO;2-9zbMath0991.91063OpenAlexW2071186660MaRDI QIDQ2714905
Publication date: 20 June 2001
Full work available at URL: https://doi.org/10.1002/1097-0037(200103)37:2<67::aid-net1>3.0.co;2-9
Related Items (18)
Edge homogeneous colorings ⋮ Computing role assignments of split graphs ⋮ Parameterizing role coloring on forests ⋮ Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ On the complexity of role colouring planar graphs, trees and cographs ⋮ Comparing Universal Covers in Polynomial Time ⋮ 2-role assignments on triangulated graphs. ⋮ Locally constrained graph homomorphisms and equitable partitions ⋮ The role assignment model nearly fits most social networks ⋮ Computing role assignments of chordal graphs ⋮ Graph coloring, minimum-diameter partitioning, and the analysis of confusion matrices ⋮ Comparing universal covers in polynomial time ⋮ Evaluating the quality of image matrices in blockmodeling ⋮ Role coloring bipartite graphs ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree ⋮ Homogeneous colourings of graphs ⋮ A complete complexity classification of the role assignment problem
Cites Work
This page was built for publication: How hard is it to determine if a graph has a 2-role assignment?
