Apakah pohon berpotongan tautan pernah digunakan dalam praktiknya, untuk perhitungan aliran maksimum atau aplikasi lain?

20

Banyak algoritma aliran max yang biasa saya lihat diimplementasikan, algoritma Dinic, push relabel, dan lainnya, dapat meningkatkan biaya waktu asimptotik melalui penggunaan pohon dinamis (juga dikenal sebagai pohon tautan-potong).

Relabel dorong berjalan di atau atau $O(V^2E)$ $O(V^3)$ normal, tetapi dengan pohon dinamis $O(V^2\sqrt{E})$ $O(VE \log(V^2/E))$
Algoritma Dinic berjalan dalam , tetapi dengan pohon dinamis $O(V^2E)$ $O(VE\log(V))$

Namun, implementasi praktis dari algoritma max-flow di sebagian besar perpustakaan tampaknya tidak memanfaatkan struktur data ini. Apakah pohon dinamis pernah digunakan dalam praktiknya untuk perhitungan aliran maksimum? Atau apakah mereka membawa terlalu banyak overhead untuk berguna untuk ukuran masalah dunia nyata?

Apakah ada domain masalah lain di mana pohon-pohon penghubung tautan digunakan?

Pertanyaan ini terkait dengan pertanyaan yang saya ajukan pada cstheory: Apakah ada yang mutakhir dari algoritma Aliran Maksimal yang praktis?

reference-request graphs data-structures network-flow Rob Lachlan
sumber

ikhtisar / desc dari link cut trees tetapi hanya menyatakan "berguna untuk aplikasi seperti Network Flow"

vzn

dari survei tarjan yang dikutip oleh reza, pada dasarnya algoritma waktu linear berkinerja sangat baik / terbaik untuk jumlah moderat dari simpul / tepi, dan kemudian ada ambang titik / tepi yang lebih besar di mana algoritma logaritmik mengungguli algoritma linear. jadi akses logaritmik fns berguna & mungkin secara signifikan lebih baik untuk grafik yang sangat besar.

vzn

7

Ada sebuah makalah berjudul " Pohon Dinamis dalam Praktek " yang mengulas implementasi praktis.

Kategori lain yang pohon Link-Cut dapat digunakan secara efisien adalah dalam Pengindeksan Basis Data . Anda dapat menemukannya di buku " Teknik Indeks Basis Data ".

Reza
sumber

pikir ini perlu beberapa elaborasi. pohon berguna untuk indeks secara umum tentu saja tetapi dalam kondisi apa pohon akan dimodifikasi?

vzn

@vzn: B + -tree, R-tree, H-Tree dan X-Tree adalah beberapa contohnya.

Reza

tentu saja, tetapi mencurigai mungkin belum ada yang mencoba menggunakan pohon link-cut dalam indeks DB sampai saat ini. ini adalah aplikasi yang masuk akal tetapi tampaknya tidak jelas bahwa mereka dioptimalkan untuk operasi yang sama yang terjadi dalam indeks DB.

vzn

5

makalah ini menemukan pada akhirnya bahwa pohon tautan-potong (LC) mengungguli pohon-pohon rake-kompres (RC) untuk algoritma Sleator / Tarjan max-flow menggunakan generator grafik acak Dimacs standar.

makalah ini berfokus pada perubahan propagasi sebagai salah satu aplikasi pohon dinamis. misalnya, perubahan propagasi mirip dengan cara sel excel spreadsheet harus dihitung ulang pada perubahan beberapa sel berdasarkan pada dependensi sel / rumus. penulis merilis kode mereka sebagai perpustakaan terbuka.

Analisis eksperimental perambatan perubahan pada pohon dinamis Acar, Blelloch, Vittes

Ubah propagasi adalah teknik untuk secara otomatis menyesuaikan output suatu algoritma dengan perubahan input. Gagasan di balik perubahan propagasi adalah untuk melacak dependensi antara panggilan data dan fungsi, sehingga, ketika input berubah, fungsi yang dipengaruhi oleh perubahan itu dapat dieksekusi kembali untuk memperbarui perhitungan dan output. Perubahan propagasi memungkinkan kompiler untuk meramalkan algoritma statis.

ay
sumber

Terima kasih. Sangat menyenangkan melihat beberapa tolok ukur algoritma yang melibatkan pohon dinamis.

Rob Lachlan

Apakah pohon berpotongan tautan pernah digunakan dalam praktiknya, untuk perhitungan aliran maksimum atau aplikasi lain?

Jawaban: