6-warna pohon secara didistribusikan

Saya mengalami beberapa kesulitan dalam memahami algoritma terdistribusi untuk pohon 6 - pewarnaan di $O(\log^*n)$ waktu.

Deskripsi lengkap dapat ditemukan di makalah berikut: Parallel Symmetry-Breaking in Sparse Graphs. Goldberg, Plotkin, Shannon .

Singkatnya, idenya adalah ...

Mulai dari pewarnaan yang valid yang diberikan oleh ID prosesor, prosedur iteratif mengurangi jumlah bit dalam deskripsi warna dengan mengubah warna setiap node nonroot $v$ dengan warna yang diperoleh dengan menyatukan indeks sedikit di mana $C_v$ berbeda dari $C_{parent}(v)$dan nilai bit ini. Akar$r$ menggabungkan $0$ dan $C_r[0]$ untuk membentuk warna barunya.

Algoritma berakhir setelah $O(\log^*n)$ iterasi.

Saya tidak memiliki pemahaman intuitif mengapa itu benar-benar berakhir $O(\log^*n)$iterasi. Seperti yang disebutkan dalam makalah pada iterasi akhir ada indeks terkecil di mana dua bit string berbeda paling banyak 3. Jadi bit ke-0 dan bit ke-1 bisa sama dan$2^2=4$, jadi dua bit ini akan memberi kita 4 warna + 2 warna lain untuk bit ke-3 yang berbeda, dan total 8 warna dan tidak 6 seperti di kertas, dan mengapa kita tidak bisa melanjutkan dengan 2 bit, masih mungkin untuk menemukan bit yang berbeda dan pisahkan mereka.

Saya akan menghargai sedikit lebih dalam analisis algoritma daripada di koran.

Dalam tulisannya, penulis menyebutkan bahwa setelah $\log^* n$iterasi, jumlah bit yang digunakan untuk mengkodekan salah satu label warna paling banyak 3. Itu berarti ada paling banyak delapan warna. Jika kita memiliki enam atau lebih sedikit warna, kita sudah selesai, dan jika tidak kita akan mengulangi loop sekali lagi.

Katakanlah kita melakukan satu iterasi loop terakhir. Root mendapat label warna 0 atau 1. Setiap node lainnya mendapat label yang sama dengan posisi bit pertama di mana label lama node tidak setuju dengan label induknya, ditambah satu bit tambahan. Sejak masuk ke iterasi ini semua warna memiliki panjang tiga bit dalam kasus terburuk, ada tiga posisi yang memungkinkan di mana bit bisa tidak setuju. Oleh karena itu, setiap warna baru dibentuk dari kombinasi satu dari tiga pilihan dan sedikit (satu dari dua pilihan), jadi pada saat keluar dari pengulangan ini hanya ada enam label warna yang mungkin, jadi kami memiliki enam warna. Jumlah total iterasi loop kemudian$\log^* n + 1 = O(\log^* n)$

Semoga ini membantu!

Algoritma Terdistribusi untuk pohon 6 - pewarnaan dalam waktu O (log * (n)) adalah algoritma yang sangat baik.

Biarkan saya jelaskan apa itu "log * n"

log * (n) - "log Star n" atau dikenal sebagai "Iterated logarithm"

Dengan kata sederhana Anda dapat menganggap log * (n) = log (log (log (..... (log * (n)))))

log * (n) sangat kuat.

Contoh:

1) Log * (n) = 5 di mana n = Jumlah atom di alam semesta

sekarang pertanyaanmu:

Mengapa itu berakhir setelah log * n waktu?

Dalam setiap putaran ukuran ID dikurangi dengan faktor log maka jumlah warna juga berkurang: untuk mengindeks bit di mana dua label ukuran n bit berbeda + 1 bit tambahan lebih banyak.

Mengapa hanya 6 warna, mengapa tidak Lebih atau Kurang?

Mengapa tidak 4 warna: {0,1,2,3} - karena dua bit diperlukan untuk mengatasi indeks yang berbeda, ditambah menambahkan "perbedaan-bit" memberi lebih dari dua bit.

Mengapa tidak 7 warna: {0,1,2,3,4,5,6} - karena 7 = 111 (dalam Binary) dapat dijelaskan dengan 3 bit, dan untuk mengatasi indeks (0,1,2) memerlukan dua bit , ditambah satu "perbedaan-bit" memberi tiga lagi.

Mengapa 6 Warna? - warna 110 (untuk warna "6") dan 111 (untuk warna "7") tidak diperlukan, karena kita dapat melakukan putaran lain! (ID tiga bit hanya dapat berbeda pada posisi 00 (untuk "0"), 01 (untuk "1"), 10 (untuk "2").

Anda dapat mengurangi 6 warna menjadi 3 warna , yang diberikan di tautan komentar Anda di atas.