An algorithmic framework for locally constrained homomorphisms
From MaRDI portal
Publication:6039418
DOI10.1007/978-3-031-15914-5_9arXiv2201.11731OpenAlexW4313005607MaRDI QIDQ6039418
Sebastian Ordyniak, Daniël Paulusma, Noleen Köhler, Konrad K. Dabrowski, Laurent Bulteau
Publication date: 5 May 2023
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2201.11731
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing role assignments of split graphs
- Sparsity. Graphs, structures, and algorithms
- Computing role assignments of proper interval graphs in polynomial time
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Computing role assignments of chordal graphs
- On the computational complexity of vertex integrity and component order connectivity
- A complete complexity classification of the role assignment problem
- Parameterizing role coloring on forests
- On the complexity of role colouring planar graphs, trees and cographs
- Computational complexity of covering three-vertex multigraphs
- Comparing universal covers in polynomial time
- On the complexity of H-coloring
- An application of simultaneous diophantine approximation in combinatorial optimization
- Finite common coverings of pairs of regular graphs
- Role colouring a graph
- Regular codes in regular graphs are difficult
- Covering regular graphs
- Conjunctive query containment revisited
- Role colouring graphs in hereditary classes
- Computational complexity of covering disconnected multigraphs
- The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- Backdoors to planning
- Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- Packing bipartite graphs with covers of complete bipartite graphs
- On the computational complexity of partial covers of theta graphs
- Homomorphisms of derivative graphs
- How hard is it to determine if a graph has a 2-role assignment?
- Complexity of Locally Injective Homomorphism to the Theta Graphs
- Locally Injective Homomorphism to the Simple Weight Graphs
- Integer Programming with a Fixed Number of Variables
- Graph labelings derived from models in distributed computing: A complete complexity classification
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Graph Layout Problems Parameterized by Vertex Cover
- Minkowski's Convex Body Theorem and Integer Programming
- Constructing 5-Arc-Transitive Cubic Graphs
- Algebraic Graph Theory
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Partial covers of graphs
- Dichotomy of the H-Quasi-Cover Problem
- SOFSEM 2005: Theory and Practice of Computer Science
- The role assignment model nearly fits most social networks
- Fixed-parameter complexity of \(\lambda\)-labelings
This page was built for publication: An algorithmic framework for locally constrained homomorphisms
