# 调和树标号算法

$g:E \rightarrow \{0,1,\ldots,n-1\}, \{v_1, v_2\} \mapsto f(v_1)+f(v_2) \mod n$

Recently I have proposed an algorithm that calculates a harmonious labelling of a given tree. This algorithm is a combination of a constraint satisfaction programming composant, a naïve backtracking procedure and a local search procedure. With this algorithm, I am able to check every tree with less than 28 nodes for harmonious labelling (took 4 days on a core of C2D T7200), which provides a limited verification of the conjecture of Graham and Sloan stating that every tree has a harmonious labelling.

This algorithm takes $O(3.75^n)$ to find a harmonious labelling for all trees with $n$ nodes. Therefore the empirical time complexity is exponential, which correspond to the fact that it is in NPC.

[1] Graceful and harmonious labellings of trees, REL Aldred, BD McKay – Bull. Inst. Combin. Appl, 1998 – Citeseer