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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Hiroshi IMAI, "Computing the Invariant Polynomials of Graphs, Networks and Matroids" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 3, pp. 330-343, March 2000, doi: .
Abstract: The invariant polynomials of discrete systems such as graphs, matroids, hyperplane arrangements, and simplicial complexes, have been theoretically investigated actively in recent years. These invariants include the Tutte polynomial of a graph and a matroid, the chromatic polynomial of a graph, the network reliability of a network, the Jones polynomial of a link, the percolation function of a grid, etc. The computational complexity issues of computing these invariants have been studied and most of them are shown to be #P-complete. But, these complexity results do not imply that we cannot compute the invariants of a given instance of moderate size in practice. To meet large demand of computing these invariants in practice, there have been proposed a framework of computing the invariants by using the binary decision diagrams (BDD for short). This provides mildly exponential algorithms which are useful to solve moderate-size practical problems. This paper surveys the BDD-based approach to computing the invariants, together with some computational results showing the usefulness of the framework.
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_330/_p
Salinan
@ARTICLE{e83-d_3_330,
author={Hiroshi IMAI, },
journal={IEICE TRANSACTIONS on Information},
title={Computing the Invariant Polynomials of Graphs, Networks and Matroids},
year={2000},
volume={E83-D},
number={3},
pages={330-343},
abstract={The invariant polynomials of discrete systems such as graphs, matroids, hyperplane arrangements, and simplicial complexes, have been theoretically investigated actively in recent years. These invariants include the Tutte polynomial of a graph and a matroid, the chromatic polynomial of a graph, the network reliability of a network, the Jones polynomial of a link, the percolation function of a grid, etc. The computational complexity issues of computing these invariants have been studied and most of them are shown to be #P-complete. But, these complexity results do not imply that we cannot compute the invariants of a given instance of moderate size in practice. To meet large demand of computing these invariants in practice, there have been proposed a framework of computing the invariants by using the binary decision diagrams (BDD for short). This provides mildly exponential algorithms which are useful to solve moderate-size practical problems. This paper surveys the BDD-based approach to computing the invariants, together with some computational results showing the usefulness of the framework.},
keywords={},
doi={},
ISSN={},
month={March},}
Salinan
TY - JOUR
TI - Computing the Invariant Polynomials of Graphs, Networks and Matroids
T2 - IEICE TRANSACTIONS on Information
SP - 330
EP - 343
AU - Hiroshi IMAI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2000
AB - The invariant polynomials of discrete systems such as graphs, matroids, hyperplane arrangements, and simplicial complexes, have been theoretically investigated actively in recent years. These invariants include the Tutte polynomial of a graph and a matroid, the chromatic polynomial of a graph, the network reliability of a network, the Jones polynomial of a link, the percolation function of a grid, etc. The computational complexity issues of computing these invariants have been studied and most of them are shown to be #P-complete. But, these complexity results do not imply that we cannot compute the invariants of a given instance of moderate size in practice. To meet large demand of computing these invariants in practice, there have been proposed a framework of computing the invariants by using the binary decision diagrams (BDD for short). This provides mildly exponential algorithms which are useful to solve moderate-size practical problems. This paper surveys the BDD-based approach to computing the invariants, together with some computational results showing the usefulness of the framework.
ER -