DAG reachability dengan O (n log n) ruang dan O (log n) -waktu permintaan?

Untuk grafik asiklik diarahkan , apakah ada struktur data yang memungkinkan untuk permintaan reachability tanpa memerlukan ruang kuadrat atau waktu linier? Idealnya saya mencari algoritma yang hanya menggunakan O (log n) ruang per titik dan waktu logaritmik di ${\langle}V,E{\rangle}$ mana . $n=|V|+|E|$

Tampaknya secara intuitif jelas bagi saya bahwa struktur data seperti ini harus ada, berdasarkan beberapa generalisasi dari algoritma pengurutan standar. Tetapi saya terkejut bahwa saya tidak dapat menemukannya. Segala sesuatu yang saya temui baik membuat asumsi tentang grafik (misalnya planaritas) atau memecahkan masalah yang lebih sulit dalam waktu kuadrat / ruang (misalnya pertanyaan yang diselingi dengan modifikasi grafik).

The Wikipedia halaman di Reachability hanya mencakup satu algoritma umum (Floyd-Warshall); sisa halaman berhubungan dengan kasus-kasus khusus yang melibatkan asumsi-asumsi seperti grafik planar (bukan).

Makalah yang paling sering dikutip dalam ruang ini tampaknya efisiensi yang diamortisasi dari struktur pengambilan jalur , tetapi ini dan semua makalah yang dikutipnya melibatkan ruang O (n ^ 2) atau waktu O (n ^ 2) untuk memungkinkan pembaruan pada grafik yang disatukan dengan permintaan (yaitu tidak ada preprocessing).

Pertanyaan ini tidak dijawab, tetapi ini berhubungan dengan masalah yang lebih sulit yaitu mengizinkan penyisipan tepi yang disatukan dengan permintaan.

Pertanyaan ini menanyakan struktur data persisten (murni fungsional), yang tidak diperlukan di sini. Kertas "Succinct Posets" membutuhkan ruang tetapi berhasil mencapai -waktu permintaan; Saya mencari algoritma waktu yang lebih buruk, lebih baik. $O(n^2)$ $O(1)$

Sebagian besar mencari pijakan dalam literatur di sini. Jika ada makalah survei tentang jangkauan grafik yang tidak menghabiskan 99% waktunya pada kasing planar, itu akan membantu.

graph-algorithms pengguna4718
sumber

Pertanyaan terkait: cstheory.stackexchange.com/questions/21503/… .

BPR

Terima kasih atas tautan RB. Pertanyaan itu dan jawaban pertama tidak berurusan dengan ruang (kecuali penyebutan singkat tentang ruang-kuadrat terikat, yang mana pertanyaan ini mencari perbaikan atas). Jawaban kedua menyinggung hasil negatif untuk kueri jarak (yaitu bilangan bulat atau bernilai nyata) daripada keterjangkauan (yaitu {0,1} -nilai) yang merupakan masalah yang lebih mudah. Terimakasih Meskipun!

user4718

Routing pintas, atau referensi yang disebutkan oleh Christian Sommer pada pertanyaan terkait, mungkin berhasil dalam praktiknya. Apakah Anda mencari pendekatan praktis atau batas bawah teoretis?

András Salamon

n^{2}

$n^2$

u

$u$

v

$v$

DAG reachability dengan O (n log n) ruang dan O (log n) -waktu permintaan?

Jawaban: