The 1-dim algoritma Weisfeiler-Lehman (WL) umumnya dikenal sebagai label kanonik atau algoritma warna perbaikan. Ia bekerja sebagai berikut:
- Pewarnaan awal seragam, untuk semua simpul .
- Dalam putaran st, warna C i + 1 ( v ) didefinisikan sebagai pasangan yang terdiri dari warna sebelumnya C i - 1 ( v ) dan multiset warna C i - 1 ( u ) untuk semua u berdekatan dengan v . Misalnya, C 1 ( v ) = C 1 ( w ) iff v dan w memiliki derajat yang sama.
- Agar penyandian warna tetap singkat, setelah setiap putaran warna diubah namanya.
Diberikan dua graf tidak berarah dan H , jika multiset warna (alias label) dari simpul G berbeda dari multiset warna dari simpul H , algoritma melaporkan bahwa grafik tersebut bukan isomorfik; jika tidak, itu menyatakan mereka sebagai isomorfik.
Sudah diketahui bahwa 1-dim WL bekerja dengan benar untuk semua pohon dan hanya membutuhkan putaran .
Pertanyaanku adalah :
Berapakah tingkat kesulitan menghitung 1-dim WL label pohon? Apakah batas bawah lebih baik daripada logspace diketahui?
sumber