Saya pikir lebih baik jika Anda hanya meminta algoritma yang paling cepat diketahui, dan bukan kebenaran dari algoritma yang diberikan dalam makalah (khususnya, lihat pertanyaan meta yang relevan ). Bagi saya, abstrak sudah merupakan bendera merah (kesimpulannya tampaknya mengandung informasi yang salah juga).
Kertas tidak lulus uji bau. Ini dimaksudkan untuk memecahkan masalah besar tetapi muncul di konferensi yang tidak jelas. Tidak ada bukti. Kebenaran "divalidasi" secara eksperimental. Para penulis berpikir bahwa grafik isomorfisme adalah NP-hard.
Sasho Nikolov
5
@ JoshuaGrochow mengatakan algoritma yang paling cepat diketahui membutuhkan waktu dalam jawaban inicstheory.stackexchange.com/a/22059/4896. Saya pikir algoritma ini deterministik. 2nlogn√
Sasho Nikolov
5
2O(nlogn√)
Jawaban:
3
penelitian tentang graf isomorfisma secara umum mengarah ke arah efisiensi atau peningkatan algoritma untuk banyak kelas grafik khusus dengan algoritma P-Time yang telah banyak mengalami kemajuan, dan juga analisis yang lebih empiris dengan perangkat lunak canggih misalnya Nauty terlihat agak rata-rata dan perilaku terburuk secara terpisah. untuk masalah umum menurut survei blog ini oleh Bennett / Flammia / Harrow ternyata hasil lama oleh Babai / Luks mungkin yang paling terkenal.
"Canonical labeling of graph" oleh László Babai dan Eugene M. Luks STOC 1983 ( makalah di sini ) Ini menggambarkan subeksponensial (atau, err, apa yang Scott memutuskan untuk menyebutnya?), Exp (-n ^ {frac {1} { 2} + c}), algoritma waktu untuk grafik dengan n simpul. Sekarang sebagai daftar bacaan saya belum merekomendasikan melompat ke makalah ini, tapi saya hanya ingin memadamkan optimisme Anda untuk algoritma klasik dengan menunjukkan kepada Anda (a) yang terbaik yang kami miliki secara umum adalah algoritma waktu subeksponensial, (b) catatan itu telah bertahan selama hampir tiga dekade, dan (c) bahwa jika Anda melihat makalah Anda dapat melihat itu tidak mudah. Abaikan harapan kamu semua yang masuk?
berikut adalah dua survei lain yang cukup komprehensif untuk mengukur yang canggih tetapi mungkin lebih dengan kecenderungan empiris.
Poin lain adalah bahwa seperti dalam jawaban JG, Graph-Isomorphism memiliki hubungan teoritis yang mendalam dengan masalah Group-Isomorphism. ini bisa dilihat di blog lain ini di subj oleh RJLipton, Suatu pendekatan untuk membuat grafik isomorfisme
vzn
Perhatikan bahwa survei Fortin berusia hampir 20 tahun, yang merupakan keabadian di bidang di mana, misalnya, konsep kelengkapan NP hanya sekitar 40 tahun.
David Richerby
ya, perhatikan juga, tetapi ada juga fenomena kunci TCS / masalah-masalah sulit yang memperlihatkan sedikit kemajuan besar selama beberapa dekade, jelas juga termasuk P vs NP sebagai contoh kanonik itu, dan GI cocok juga seperti yang dinyatakan.
vzn
Anda tampaknya membingungkan pernyataan "Kami belum menyelesaikan masalah" dan "belum ada kemajuan."
Jawaban:
penelitian tentang graf isomorfisma secara umum mengarah ke arah efisiensi atau peningkatan algoritma untuk banyak kelas grafik khusus dengan algoritma P-Time yang telah banyak mengalami kemajuan, dan juga analisis yang lebih empiris dengan perangkat lunak canggih misalnya Nauty terlihat agak rata-rata dan perilaku terburuk secara terpisah. untuk masalah umum menurut survei blog ini oleh Bennett / Flammia / Harrow ternyata hasil lama oleh Babai / Luks mungkin yang paling terkenal.
berikut adalah dua survei lain yang cukup komprehensif untuk mengukur yang canggih tetapi mungkin lebih dengan kecenderungan empiris.
Algoritma Efisien untuk Pengujian Grafik Isomorfisme Jose Luis Lopez Presa PhD tesis (2009)
The Graph Isomorphism Problem (1996) Fortin (1996)
sumber
sumber