Exact algorithm for graph homomorphism and locally injective graph homomorphism

DOI10.1016/j.ipl.2014.02.012zbMath1285.05130arXiv1310.3341OpenAlexW1494193561WikidataQ62595912 ScholiaQ62595912MaRDI QIDQ2446599

Paweł Rzążewski

Publication date: 17 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.3341

zbMATH Keywords

graph homomorphismgraph algorithmsexact algorithmlocally injective homomorphism\(H(2, 1)\)-labeling

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Lower Bounds for the Graph Homomorphism Problem ⋮ Unnamed Item ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• A complete complexity classification of the role assignment problem
• On the complexity of H-coloring
• Covering regular graphs
• On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs
• On the computational complexity of partial covers of theta graphs
• Exact algorithms for graph homomorphisms
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• Set Partitioning via Inclusion-Exclusion
• Labelling Graphs with a Condition at Distance 2
• Circular Distance Two Labeling and the $\lambda$-Number for Outerplanar Graphs
• Circular chromatic number: A survey

This page was built for publication: Exact algorithm for graph homomorphism and locally injective graph homomorphism