1-wym algorytm Weisfeiler-Lehman (WL) jest powszechnie znany jako kanonicznej oznakowania lub algorytmu kolor rafinacji. Działa w następujący sposób:
- Początkowe zabarwienie jest jednolite, C 0 ( v ) = 1 dla wszystkich wierzchołków v ∈ V ( G ) ∪ V ( H ) .
- W rundzie, kolor C i + 1 ( v ) jest zdefiniowany jako para składająca się z poprzedzającego koloru C i - 1 ( v ) i multisetutu kolorów C i - 1 ( u ) dla wszystko u sąsiaduje z v . Na przykład C 1 ( v ) = C 1 ( w ) iff v i w mieć ten sam stopień.
- Aby kodowanie kolorów było krótkie, po każdej rundzie zmienia się nazwy kolorów.
Biorąc pod uwagę dwa nieukierowane wykresy i H , jeśli multisetta kolorów (inaczej etykiety) wierzchołków G różni się od multisetta kolorów wierzchołków H , algorytm zgłasza, że wykresy nie są izomorficzne; w przeciwnym razie deklaruje je jako izomorficzne.
Powszechnie wiadomo, że 1-dim WL działa poprawnie dla wszystkich drzew i wymaga tylko rund .
Moje pytanie brzmi :
Jaka jest twardość obliczania 1-dimowych etykiet WL drzewa? Czy dolna granica jest lepsza niż logspace?
źródło