Goldberg & Tarjan: Cara menemukan aliran pemblokiran dalam grafik

8

Saya ingin menerapkan algoritma Goldberg & Rao untuk menemukan maxflow dalam grafik. Masalah saya adalah langkah pembaruan di mana setiap kertas dan laporan menyatakan "Dalam grafik yang dihasilkan, temukan aliran pemblokiran atau aliran nilai Delta." Mereka semua merujuk ke Goldberg & Tarjan untuk menemukan aliran pemblokiran. Ada dua hal yang saya tidak mengerti:

  1. Bagaimana saya bisa menemukan aliran nilai Delta?
  2. Tetapi yang lebih penting: bagaimana saya bisa menemukan aliran pemblokiran?

Mengenai pertanyaan 2: Saya membaca dua makalah (yang oleh Goldberg & Tarjan "Pendekatan Baru untuk Masalah Aliran Maksimum" dan yang tentang pohon dinamis - keduanya tidak terlalu sulit untuk dipahami). Setiap makalah / laporan / buku tentang Goldberg & Rao mengacu pada makalah oleh Goldberg & Tarjan dan menyoroti bahwa Goldberg & Rao tidak menggunakan algoritma push / relabel tetapi menemukan aliran pemblokiran. Tetapi menurut saya, Tarjan hanya menjelaskan algoritma push / relabel, saya tidak dapat menemukan apa pun tentang memblokir aliran.

T. Cormen, "Pengantar algoritma", edisi ke-3

O(min(V2/3,E1/2)Elg(V2/E+2)lgC)C=maxc(u,v)

A. Goldberg & S. Rao, "Beyond the Flow Decomposition Barrier" (kertas asli)

Dengan menggunakan algoritma aliran pemblokiran Goldberg dan Tarjan [1988], kita mendapatkan ikatan .O(Λmlog(n2/m)logU)

pengguna1904159
sumber

Jawaban:

5

Mereka memberikan referensi yang salah, untuk alasan apa pun, seperti yang telah Anda temukan sendiri.

Metode aliran pemblokiran yang seharusnya Anda gunakan adalah metode yang diberikan

http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-333.pdf , Bagian 8.3.

Olaf
sumber
Terima kasih! Anda sangat membantu saya! :) (maaf atas balasan saya yang terlambat)
user1904159