Pada Grafik Isomorfisme Masalah Lengkap

11

Saya tertarik untuk mempelajari masalah lengkap Graph Isomorphism (GI).

Dalam Makalah "Masalah Polinomi Setara dengan Isomorfisme Grafik" oleh Kellogg S. Booth, (1979), terbukti bahwa banyak masalah dasar adalah GI lengkap dengan menggunakan teknik penggantian Edge, teknik komposisi dll.

Saya ingin belajar beberapa teknik yang digunakan dalam makalah baru-baru ini.

Dapatkah seseorang menyarankan saya beberapa makalah baru-baru ini yang lebih terkonsentrasi dalam membuktikan beberapa kelas grafik adalah GI lengkap.

cc.complexity-theory reference-request graph-isomorphism Kumar
sumber
4
lihat juga wikipedia graph isomorphism complete & GI-hard problems
vzn
2
Apa yang telah Anda lakukan, untuk mencoba mencari kertas sendiri? Sudahkah Anda mencoba menggunakan metode pencarian literatur standar (mis. Mencari di Google Cendekia, menemukan semua kertas yang mengutip kertas Booth, dll.)?
DW

Jawaban:

4

Dalam tulisan ini, kami membuktikan bahwa menentukan isomorfisme dari grafik split ganda, kelas grafik yang menunjukkan 2-join, dan kelas grafik yang menunjukkan partisi condong yang seimbang adalah GI-complete. Lebih lanjut, kami menunjukkan bahwa masalah GI untuk kelas yang lebih besar termasuk kelas grafik ini - yaitu, kelas grafik sempurna - juga merupakan GI lengkap.

vzn
sumber
@ emas bagus; ia melompat keluar kepada saya di antara berbagai alternatif antara lain karena grafik sempurna tampaknya memiliki banyak koneksi mendalam ke teori kompleksitas & tampaknya memiliki beberapa ikatan besar yang belum ditemukan tetapi "di cakrawala".
vzn