A complete complexity classification of the role assignment problem
From MaRDI portal
Publication:817773
DOI10.1016/j.tcs.2005.09.029zbMath1124.91055OpenAlexW2039709665MaRDI QIDQ817773
Publication date: 20 March 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.029
Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Computing role assignments of split graphs, Parameterizing role coloring on forests, Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings, List covering of regular multigraphs, An algorithmic framework for locally constrained homomorphisms, On the complexity of role colouring planar graphs, trees and cographs, Graph covers: where topology meets computer science, and simple means difficult, Comparing Universal Covers in Polynomial Time, Tree-representation of set families and applications to combinatorial decompositions, List covering of regular multigraphs with semi-edges, Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs, Locally constrained graph homomorphisms and equitable partitions, Unnamed Item, The Complexity of Boolean Surjective General-Valued CSPs, \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs, The complexity of surjective homomorphism problems-a survey, Computing role assignments of proper interval graphs in polynomial time, Packing bipartite graphs with covers of complete bipartite graphs, Locally constrained graph homomorphisms -- structure, complexity, and applications, Exact algorithm for graph homomorphism and locally injective graph homomorphism, Labelled (Hyper)Graphs, Negotiations and the Naming Problem, On the power of synchronization between two adjacent processes, Computing Role Assignments of Proper Interval Graphs in Polynomial Time, Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees, Surjective \(H\)-colouring: new hardness results, Computing role assignments of chordal graphs, Computing vertex-surjective homomorphisms to partially reflexive trees, Finding vertex-surjective graph homomorphisms, Comparing universal covers in polynomial time, Role colouring graphs in hereditary classes, A Representation Theorem for Union-Difference Families and Application, Subexponential algorithms for variants of the homomorphism problem in string graphs, Graph labelings derived from models in distributed computing: A complete complexity classification, Role coloring bipartite graphs, Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
Cites Work
- Finite common coverings of pairs of regular graphs
- Role colouring a graph
- Covering regular graphs
- How hard is it to determine if a graph has a 2-role assignment?
- Constructing 5-Arc-Transitive Cubic Graphs
- Partial covers of graphs
- Fixed-parameter complexity of \(\lambda\)-labelings
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
