O algoritmo Weisfeiler-Lehman (WL) 1-dim é comumente conhecido como rotulagem canônica ou algoritmo de refinamento de cores. Funciona da seguinte maneira:
- A coloração inicial é uniforme, C 0 ( v ) = 1 para todos os vértices v ∈ V ( G ) ∪ V ( H ) .
- Na rodada , a cor C i + 1 ( v ) é definida como um par que consiste na cor anterior C i - 1 ( v ) e no conjunto múltiplo de cores para todos os adjacentes a . Por exemplo, sse v e w têm o mesmo grau.
- Para manter a codificação de cores curta, após cada rodada, as cores são renomeadas.
Dado dois gráficos não direcionados e H , se o multiset de cores (também conhecido como rótulos) dos vértices de G for distinto do multiset de cores dos vértices de H , o algoritmo relata que os gráficos não são isomórficos; caso contrário, declara-os isomórficos.
É sabido que o WL 1-dim funciona corretamente para todas as árvores e requer apenas rodadas .
Minha pergunta é :
Qual é a dureza de calcular etiquetas WL 1-dim de uma árvore? Um limite inferior é melhor que o espaço de registro conhecido?
fonte