The Existence of Homomorphisms to Oriented Cycles
From MaRDI portal
Publication:4837649
DOI10.1137/S0895480192239992zbMath0831.05059MaRDI QIDQ4837649
Publication date: 12 February 1996
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
computational complexity; homomorphism; digraphs; NP-complete; oriented path; oriented cycle; backward arcs; forward arcs
Related Items
Dualities for Constraint Satisfaction Problems, Minimum cost homomorphism dichotomy for oriented cycles, A surprising permanence of old motivations (a not-so-rigid story), Homomorphisms to oriented paths, The complexity of restricted graph homomorphisms, Homomorphisms and oriented colorings of equivalence classes of oriented graphs, Complexity of tree homomorphisms, Minimum Cost Homomorphism Dichotomy for Oriented Cycles