Exact algorithm for graph homomorphism and locally injective graph homomorphism

DOI10.1016/j.ipl.2014.02.012zbMath1285.05130arXiv1310.3341WikidataQ62595912 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 homomorphism; graph algorithms; exact algorithm; locally injective homomorphism; \(H(2, 1)\)-labeling

Mathematics Subject Classification ID

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

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

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