Bab 1 buku Metode Probabilistik, oleh Alon dan Spencer menyebutkan masalah berikut:
Diberikan grafik , putuskan apakah konektivitas tepinya setidaknya n / 2 atau tidak.
Penulis menyebutkan adanya sebuah algoritma oleh Matula dan meningkatkan ke O ( n 8 / 3 log n ) .
Pertanyaan saya adalah, apa waktu berjalan paling dikenal untuk masalah ini?
Biarkan saya menggambarkan algoritma yang ditingkatkan.
Pertama, putuskan apakah memiliki tingkat minimum setidaknya n / 2 atau tidak. Jika tidak, maka konektivitas tepi jelas kurang dari n / 2 .
Selanjutnya, jika bukan itu masalahnya, hitung himpunan dominan dari G ukuran O ( log n ) . Ini dapat dilakukan dalam waktu O ( n 2 ) , dengan suatu algoritma yang dijelaskan dalam bagian buku sebelumnya.
Selanjutnya, ia menggunakan hal-hal berikut yang tidak terlalu sulit untuk membuktikan fakta:
Jika derajat minimum adalah , maka untuk setiap pemotongan tepi paling banyak δ yang membagi V menjadi V 1 dan V 2 , setiap rangkaian G yang mendominasi harus memiliki simpulnya dalam V 1 dan V 2 .
Sekarang perhatikan himpunan dominan . Sejak G memiliki minimal gelar n / 2 , setiap potong tepi ukuran kurang dari n / 2 juga harus memisahkan U . Jadi untuk setiap i ∈ { 2 , k } , kami menemukan ukuran potongan tepi terkecil yang memisahkan u 1 dan u i . Masing-masing dari hal-hal ini dapat dilakukan dalam waktu O ( n 8 / 3 menggunakan algoritma max-flow. Jadi total waktu yang diambil adalah O ( n 8 / 3 log n ) .
sumber
Jawaban:
Strangely enough, the only reference I find to this result is this from a bioinformatics conference. I'd be really curious to see whether it has been proven somewhere else.
Edit: An earlier reference is: Gary Chartrand: A Graph-Theoretic Approach to a Communications Problem, SIAM J. Appl. Math. 14-4 (1966), pp. 778-781.
sumber