Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Two-Stage Discrete Optimization Method for Largest Common Subgraph Problems Kaedah Pengoptimuman Diskret Dua Peringkat untuk Masalah Subgraf Biasa Terbesar

Nobuo FUNABIKI, Junji KITAMICHI

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Algoritma pengoptimuman gabungan baru dipanggil Kaedah pengoptimuman diskret 2 peringkat (2DOM) dicadangkan untuk masalah subgraf biasa (LCSP) terbesar dalam kertas ini. Diberi dua graf G=(V1, E1) dan H=(V2, E2), matlamat LCSP adalah untuk mencari subgraf G'=(V1', E1') daripada G dan subgraf H'=(V2', E2') daripada H seperti itu G' and H' bukan sahaja isomorfik antara satu sama lain tetapi juga bilangan tepinya dimaksimumkan. Kedua-dua graf G' and H' adalah isomorfik apabila |V1'|=|V2'| dan |E1'|=|E2'|, dan wujud surat-menyurat satu-dengan-satu puncak f: V1' V2' seperti itu {u, v} E1' jika dan hanya jika{f(u), f(v)} E2'. LCSP dikenali sebagai NP-lengkap secara umum. 2DOM terdiri daripada peringkat pembinaan dan peringkat penghalusan untuk mencapai kualiti penyelesaian yang tinggi dan masa pengiraan yang singkat untuk masalah pengoptimuman gabungan yang sukar bersaiz besar. Peringkat pembinaan mencipta penyelesaian awal yang boleh dilaksanakan dengan kualiti yang tinggi, berdasarkan kaedah heuristik yang tamak. Peringkat penghalusan meningkatkannya dengan mengekalkan kebolehlaksanaan, berdasarkan kaedah keturunan diskret rawak. Prestasi dinilai dengan menyelesaikan dua jenis kejadian 1200 LCSP yang dijana secara rawak dengan maksimum 500 bucu untuk G dan 1000 bucu untuk H. Keputusan simulasi menunjukkan keunggulan 2DOM kepada penyepuhlindapan simulasi dari segi kualiti penyelesaian dan masa pengiraan.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E82-D No.8 pp.1145-1153
Tarikh penerbitan
1999/08/25
Diumumkan
ISSN dalam talian
DOI
Jenis Manuskrip
PAPER
kategori
Algoritma dan Kerumitan Pengiraan

Pengarang

Kata kunci

Contents [show]