Saya bertanya-tanya bagaimana menemukan ketebalan grafik tidak berarah jarang. Maksud saya jarang . Maksud saya adalah kompleksitas waktu terendah.
Saya memikirkan beberapa modifikasi pada algoritma Tarjan untuk grafik tidak berarah, tetapi saya tidak menemukan hasil yang baik. Sebenarnya saya berpikir bahwa jika saya dapat menemukan 2 komponen yang terhubung di , maka saya dapat menemukan ketebalannya, dengan semacam induksi yang dapat dicapai dari bagian pertama. Saya mungkin berada di jalur yang salah. Algoritma apa pun asimtotik lebih baik dari Θ ( | V | 2 ) (yaitu o ( | V | 2 ) ) diterima.
Jawaban:
Inilah yang saya ketahui tentang masalah ketebalan dalam grafik tidak tertimbang yang tidak diarahkan. Pertama-tama, jika ketebalannya genap, Anda dapat menentukannya dalam waktu - ini adalah hasil lama dari Itai dan Rodeh (A. Itai dan M. Rodeh. Menemukan rangkaian minimum dalam grafik. SIAM J Computing, 7 (4): 413–423, 1978.). Idenya ada: untuk setiap simpul dalam grafik, mulai BFS sampai siklus pertama ditutup (kemudian berhenti dan pindah ke simpul berikutnya); kembalikan siklus terpendek yang ditemukan. Jika lingkar bahkan siklus terpendek ditemukan akan menjadi siklus terpendek. Khususnya jika grafik Anda adalah bipartit, ini akan selalu menghitung ketebalannya. Namun, jika ketebalan g aneh, Anda akan menemukan siklus panjang g atau g +O(n2) g g , jadi Anda mungkin libur 1 .g+1 1
Sekarang, masalah sebenarnya dengan ketebalan aneh adalah bahwa mau tidak mau algoritma Anda harus dapat mendeteksi jika grafik memiliki segitiga. Algoritma terbaik untuk itu menggunakan perkalian matriks: min { n 2.38 , m 1.41 ) waktu untuk grafik pada n node dan m edge. Itai dan Rodeh juga menunjukkan bahwa algoritma apa pun yang dapat menemukan segitiga dalam grafik padat juga dapat menghitung ketebalannya, jadi kami memiliki algoritma ketebalan waktu O ( n 2.38 ) . Namun, runtime untuk ketebalan dalam grafik jarang tidak sebagus untuk menemukan segitiga. Yang terbaik yang kita tahu secara umum adalah O ( mO( n2.38,m1.41) n m O(n2.38) . Secara khusus, apa yang tampaknya paling sulit adalah menemukanalgoritma waktu o ( n 2 ) untuk grafik dengan m = O ( n ) .O(mn) o(n2) m=O(n)
sumber
Menemukan ketebalan grafik planar memiliki sejarah yang menarik. Lihat makalah ini oleh Chang dan Lu untuk algoritma waktu linier dan sejarah perbaikan.
Tidak ada teknik umum untuk menemukan ketebalan dari setiap grafik jarang. Seringkali kita harus melihat dekomposisi khusus yang terkait atau embeddings untuk mencapai batas yang lebih baik. Jika grafik "terbukti" jarang, seringkali ada struktur bagus yang terkait dengannya. Sebagai contoh, grafik treewidth terikat terbatas dan mereka memiliki dekomposisi pohon terkait.
Mendesain ao ( n2) Algoritma untuk grafik jarang umum adalah masalah terbuka.
sumber