Kratsch, Dieter


Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

\begin{question} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. Is there an algorithm that decides, for input graphs $G$ and $H$, whether there exists a homomorphism from $G$ to $H$ in time $O(c^{|V(G)|+|V(H)|})$ for some constant $c$? \end{question}

Keywords: algorithm; Exponential-time algorithm; homomorphism

Syndicate content