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

Computing the Invariant Polynomials of Graphs, Networks and Matroids Mengira Polinomial Invarian Graf, Rangkaian dan Matroid

Hiroshi IMAI

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Polinomial invarian sistem diskret seperti graf, matroid, susunan hyperplane, dan kompleks ringkas, telah secara teorinya disiasat secara aktif dalam beberapa tahun kebelakangan ini. Invarian ini termasuk polinomial Tutte bagi graf dan matroid, polinomial kromatik graf, kebolehpercayaan rangkaian rangkaian, polinomial Jones bagi pautan, fungsi perkolasi grid, dll. Isu kerumitan pengiraan pengiraan ini invarian telah dikaji dan kebanyakannya ditunjukkan sebagai #P-lengkap. Tetapi, keputusan kerumitan ini tidak membayangkan bahawa kita tidak boleh mengira invarian bagi contoh saiz sederhana tertentu dalam amalan. Untuk memenuhi permintaan yang besar dalam pengiraan invarian ini dalam amalan, telah dicadangkan rangka kerja pengiraan invarian dengan menggunakan gambar rajah keputusan binari (pendek kata BDD). Ini menyediakan algoritma eksponen sederhana yang berguna untuk menyelesaikan masalah praktikal bersaiz sederhana. Kertas kerja ini meninjau pendekatan berasaskan BDD untuk mengira invarian, bersama-sama dengan beberapa keputusan pengiraan yang menunjukkan kegunaan rangka kerja.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.330-343
Tarikh penerbitan
2000/03/25
Diumumkan
ISSN dalam talian
DOI
Jenis Manuskrip
INVITED SURVEY PAPER
kategori
Algoritma untuk Matroid dan Sistem Diskret Berkaitan

Pengarang

Kata kunci

Contents [show]