A complete complexity classification of the role assignment problem
From MaRDI portal
Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30)
Recommendations
Cites work
- Constructing 5-Arc-Transitive Cubic Graphs
- Covering regular graphs
- Finite common coverings of pairs of regular graphs
- Fixed-parameter complexity of \(\lambda\)-labelings
- How hard is it to determine if a graph has a 2-role assignment?
- scientific article; zbMATH DE number 91031 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1202982 (Why is no real title available?)
- scientific article; zbMATH DE number 1953094 (Why is no real title available?)
- scientific article; zbMATH DE number 2080268 (Why is no real title available?)
- scientific article; zbMATH DE number 2081019 (Why is no real title available?)
- Partial covers of graphs
- Role colouring a graph
Cited in
(45)- Surjective \(H\)-colouring: new hardness results
- Role colouring graphs in hereditary classes
- Role coloring bipartite graphs
- List covering of regular multigraphs
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- Locally constrained graph homomorphisms and equitable partitions
- Packing bipartite graphs with covers of complete bipartite graphs
- Exact algorithm for graph homomorphism and locally injective graph homomorphism
- How hard is it to determine if a graph has a 2-role assignment?
- Computing role assignments of split graphs
- Computing role assignments of proper interval graphs in polynomial time
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Graph labelings derived from models in distributed computing: A complete complexity classification
- Comparing Universal Covers in Polynomial Time
- Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
- Labelled (Hyper)Graphs, Negotiations and the Naming Problem
- Tree-representation of set families and applications to combinatorial decompositions
- The complexity of surjective homomorphism problems-a survey
- scientific article; zbMATH DE number 2038757 (Why is no real title available?)
- Computing role assignments of proper interval graphs in polynomial time
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- The Complexity of Boolean Surjective General-Valued CSPs
- Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings
- A Representation Theorem for Union-Difference Families and Application
- scientific article; zbMATH DE number 7651213 (Why is no real title available?)
- The role assignment model nearly fits most social networks
- An algorithmic framework for locally constrained homomorphisms
- Computing role assignments of Cartesian product of graphs
- Graph covers: where topology meets computer science, and simple means difficult
- List covering of regular multigraphs with semi-edges
- \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs
- An algorithmic framework for locally constrained homomorphisms
- Study on (r+1)-role assignments of complementary prisms, with r 3
- On the power of synchronization between two adjacent processes
- Computing a 3-role assignment is polynomial-time solvable on complementary prisms
- Tabular intermediate logics comparison
- Computational complexity of covering multigraphs with semi-edges: small cases
- Computing role assignments of chordal graphs
- Computing vertex-surjective homomorphisms to partially reflexive trees
- Finding vertex-surjective graph homomorphisms
- Computational complexity of covering regular trees
- Parameterizing role coloring on forests
- On the complexity of role colouring planar graphs, trees and cographs
- Comparing universal covers in polynomial time
This page was built for publication: A complete complexity classification of the role assignment problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817773)
