Algoritma Pencacahan Klik

9

Saya membaca kertas tua MC Golumbic tentang grafik EPT (persimpangan jalur di pohon). Dalam makalah itu ditunjukkan bahwa jumlah klik maksimal dari instance grafik EPT adalah polinomial. Disimpulkan bahwa jika oracle melaporkan bahwa grafik adalah grafik EPT, maka dimungkinkan untuk menemukan klik maksimum dengan algoritma enumerasi klik standar.G

Pertama-tama, apa saja algoritma enumerasi klik standar ini? Jika ada lebih dari satu, dapatkah kita mengatakan bahwa jika jumlah klik maksimum grafik adalah polinomial maka dapatkah kita menggunakan salah satu dari algoritma enumerasi ini? Atau haruskah kita mendapatkan algoritma khusus dari algoritma generik yang menggunakan beberapa struktur khusus dari kelas grafik?

Terima kasih sebelumnya.

ds.algorithms graph-algorithms clique Arman
sumber

Jawaban:

13

Ada beberapa algoritma sensitif-keluaran untuk menghitung semua klik maksimal dalam waktu polinomial per keluaran. Salah satu algoritma paling awal dikembangkan oleh Tsukiyama, Ide, Ariyoshi, dan Shirakawa (1977).

  • Shuji Tsukiyama, Ide Mikio, Hiromu Ariyoshi, Isao Shirakawa: Algoritma Baru untuk Menghasilkan Semua Set Independen Maksimal. SIAM J. Comput. 6 (3): 505-517 (1977)

Ini berarti bahwa jika Anda tahu grafik Anda memiliki paling banyak polinomially klik maksimum, maka total waktu berjalan dari algoritma mereka akan polinomial dalam ukuran input.

Yoshio Okamoto
sumber
Sayangnya, saya tidak memiliki akses ke kertas. Tapi saya yakin ini yang saya cari, terima kasih.
Arman
4

Algoritma Bron – Kerbosch menghitung semua klik maksimal dalam grafik yang tidak terarah (lihat Wikipeadia ). Waktu lari terburuk adalah O (3 n / 3 ), tampaknya itu sangat cepat secara umum dan masih merupakan algoritma yang paling cepat diketahui untuk menghitung semua klik maksimal. Untuk referensi yang lebih baru lihat makalah V. Stix dan Cazals dan Karande .

Volker Turau
sumber
2
HAI(3n/3)3n/33n/3K3,3,...,3
1
Untuk pekerjaan terbaru tentang Bron – Kerbosch, lihat makalah saya arxiv.org/abs/1006.5440 dengan Strash dan Löffler di ISAAC 2010 dan arxiv.org/abs/1103.0318 dengan Strash di SEA 2011. Namun ini tidak benar-benar menjawab pertanyaan poster asli karena algoritmanya tidak peka-keluaran: ia bisa membutuhkan waktu yang eksponensial bahkan ketika hanya ada banyak klik maksimal secara polinomi.
David Eppstein