2024-03-28T20:38:00Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000318702023-04-27T10:00:04Z01164:02592:02620:02625
混合探索による順序を用いたJones多項式の計算手法Computation of the Jones Polynomials using mixed searchjpnhttp://id.nii.ac.jp/1001/00031870/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31870&item_no=1&attribute_id=1&file_no=1Copyright (c) 2004 by the Information Processing Society of Japan中央大学大学院理工学研究科情報工学専攻中央大学理工学部情報工学科内海, 友雄今井, 桂子結び目の不変量の1つにJones多項式があるが,これを計算することは#P-困難であることが知られている. 二分決定グラフ(Binary Decision Diagram;BDD)を用いたJones多項式の計算においては,BDDの幅がJones多項式計算の計算量を決定する.本稿ではBDDの幅が結び目のTaitグラフの混合探索数と関係があることを示す.混合探索数の近似解を計算することのできる外平面グラフをTaitグラフとして持つ結び目に対して,Taitグラフの枝数をmとした時,BDDを用いることによってJones多項式がO(m^2)で計算できることを示す.The Jones polynomial is one of the invariants in knot theory, and it is known that computing the Jones polynomial of a knot is #P-hard. We consider the problem of computing the Jones polynomials and we use Binary Decision Diagram(BDD) for this problem. We present that the width of the BDD has a strong connection with the mixed search number of the Tait graph for the knot. We show the Jones polynomial for a knot whose Tait graph is outerplanar can be computed in O(m^2) time, where m is the number of edges in the Tait graph. Computational results are also shown.AN1009593X情報処理学会研究報告アルゴリズム(AL)200434(2003-AL-094)951002004-03-192009-06-30