Apa algoritma deterministik tercepat untuk pencapaian digraph dinamis tanpa penghapusan tepi?

16

Apa hasil deterministik terbaik untuk mempertahankan penutupan transitif dinamis dalam grafik terarah dengan hanya penyisipan tepi?

Saya membaca beberapa makalah tentang masalah penutupan transitif dinamis dengan kedua penyisipan tepi dan penghapusan. Namun, apakah ada algoritma yang lebih baik untuk itu dengan hanya penyisipan tepi?

ds.algorithms graph-theory graph-algorithms dynamic-algorithms wei wang
sumber
3
Bukankah ini dipecahkan oleh struktur data union-find?
Tyson Williams
Apakah grafik Anda diarahkan atau tidak diarahkan? @TysonWilliams benar karena untuk grafik tidak berarah tanpa penghapusan tepi, Anda pada dasarnya hanya melakukan pencarian gabungan (setiap penyisipan adalah operasi UNION)
Suresh Venkat
1
Ah .. saya lupa menyebutkan, itu digraf. Buruk saya .... akan diperbarui kemudian.
wei wang

Jawaban:

9

HAI(n)

virgi
sumber