Finding Vertex-Surjective Graph Homomorphisms

DOI10.1007/978-3-642-30642-6_16zbMath1360.68511arXiv1204.2124MaRDI QIDQ2907498

Daniël Paulusma, Petr A. Golovach, Barnaby Martin, Bernard Lidický

Publication date: 10 September 2012

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

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

Related Items

The complexity of surjective homomorphism problems-a survey, Computing vertex-surjective homomorphisms to partially reflexive trees