{"created":"2021-03-01T07:09:46.499178+00:00","id":48954,"links":{},"metadata":{"_buckets":{"deposit":"e2d913ff-0dd0-4b07-b9e8-0060a55f9fc6"},"_deposit":{"id":"48954","owners":[],"pid":{"revision_id":0,"type":"depid","value":"48954"},"status":"published"},"_oai":{"id":"oai:repository.dl.itc.u-tokyo.ac.jp:00048954","sets":["34:95:96","9:10:15"]},"item_2_biblio_info_7":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2000-03-25","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicPageEnd":"343","bibliographicPageStart":"330","bibliographicVolumeNumber":"E83-D","bibliographic_titles":[{"bibliographic_title":"IEICE TRANSACTIONS on Information and Systems"}]}]},"item_2_description_5":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Abstract"}]},"item_2_description_6":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"INVITED SURVEY PAPER","subitem_description_type":"Other"}]},"item_2_publisher_20":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Institute of Electronics, Information and Communication Engineers"}]},"item_2_relation_25":{"attribute_name":"関係URI","attribute_value_mlt":[{"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://search.ieice.org/","subitem_relation_type_select":"URI"}}]},"item_2_rights_12":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"copyright©2000 IEICE"}]},"item_2_select_14":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_select_item":"publisher"}]},"item_2_text_4":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Department of Information Science, University of Tokyo"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"IMAI, Hiroshi"}],"nameIdentifiers":[{"nameIdentifier":"145472","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-12-15"}],"displaytype":"detail","filename":"Computing the Invariant Polynomials of Graphs_ Networks and Matroids  2000.pdf","filesize":[{"value":"525.8 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"Computing the Invariant Polynomials of Graphs_ Networks and Matroids  2000.pdf","url":"https://repository.dl.itc.u-tokyo.ac.jp/record/48954/files/Computing the Invariant Polynomials of Graphs_ Networks and Matroids  2000.pdf"},"version_id":"b0fd2e6d-08de-4b39-9750-f6445069783e"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Computing the Invariant Polynomials of Graphs, Networks and Matroids","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Computing the Invariant Polynomials of Graphs, Networks and Matroids"}]},"item_type_id":"2","owner":"1","path":["15","96"],"pubdate":{"attribute_name":"公開日","attribute_value":"2017-12-14"},"publish_date":"2017-12-14","publish_status":"0","recid":"48954","relation_version_is_last":true,"title":["Computing the Invariant Polynomials of Graphs, Networks and Matroids"],"weko_creator_id":"1","weko_shared_id":null},"updated":"2022-12-19T04:23:38.001130+00:00"}