Algoritma paralel untuk dapat dijangkau dalam grafik planar terarah

$O({\log}n)$ $O(m+n)$

Apa algoritma paralel yang paling dikenal untuk st-konektivitas dalam grafik planar terarah?

Silakan sebutkan waktu berjalan, algoritma deterministik / acak dan model PRAM yang digunakan (dengan asumsi jumlah prosesor adalah polinomial).

Pertanyaan ini terkait dengan salah satu pertanyaan saya sebelumnya. Pertanyaan saya sebelumnya adalah tentang grafik diarahkan umum yang belum tentu planar.

ds.algorithms graph-theory dc.parallel-comp Siwa Kintali
sumber

Butuh beberapa klik bolak-balik untuk menyadari bahwa perbedaannya adalah planaritas. dapatkah Anda menjelaskannya ketika Anda menyebutkan pertanyaan sebelumnya?

Suresh Venkat

Saya melakukan hal yang sama dengan Suresh, dan saya bebas mengedit kalimat terakhir. Kata "umum" tidak terlalu informatif ketika pembaca tidak tahu apa yang bertentangan dengan ("planar" dalam kasus ini). Saya harap Anda tidak keberatan ....

Tsuyoshi Ito

Jawaban:

Lihat

Kao, Ming-Yang; Klein, Philip N. (1993), Menuju mengatasi bottleneck transitif-penutupan: algoritma paralel yang efisien untuk digraf planar, J. Comput. Sistem Sci. 47 (1993), no. 3, 459–500.

Teorema 10 mereka memberikan algoritma CRCW deterministik untuk $st$ -terjangkau dalam digraf planar dengan $O(n)$ prosesor dan $O(\log^3 n)$ waktu. Mencari Google Cendekia untuk makalah lain yang mengutip makalah mereka, saya tidak melihat orang lain dengan perbaikan ini.

David Eppstein
sumber