混合探索による順序を用いたJones多項式の計算手法
スポンサーリンク
概要
- 論文の詳細を見る
結び目の不変量の1つにJones多項式があるが,これを計算することは#P-困難であることが知られている.二分決定グラフ(Binary Decision Diagram; BDD)を用いたJones多項式の計算においては,BDDの幅がJones多項式計算の計算量を決定する.本稿ではBDDの幅が結び目のTaitグラフの混合探索数と関係があることを示す.混合探索数の近似解を計算することのできる外平面グラフをTaitグラフとして持つ結び目に対して. Taitグラフの枝数をmとした時,BDDを用いることによってJones多項式がO(m^2)で計算できることを示す.
- 一般社団法人情報処理学会の論文
- 2004-03-19
著者
関連論文
- 安全性を考慮した集団下校経路の作成 : 階層型施設配置モデルの適用(子どもを守る・育む)
- 日本応用数理学会創立10周年記念講演会 : パネル討論会「応用数理の未来」(10周年記念)
- 入力された形状を考慮したスケッチによるメッシュの表面特徴の変形(セッション2:モデリング・認識)
- 2-C-9 地図の拡大・縮小表示を念頭に置いたNLP問題に対するラベルサイズ最大化(公共関連(2))
- 制御点を用いたメッシュ変形手法
- Open Surfaceメッシュに対するPolyCube Mapの構築
- 対話型操作におけるメッシュ分割アルゴリズムの高速化
- Isophotic Metric を用いたペーパークラフトモデルの作製
- 距離等分の存在
- 量子純粋状態のボロノイ図について