Tutte多項式の計算とBDD
スポンサーリンク
概要
- 論文の詳細を見る
グラフのTutte多項式を計算する問題は、グラフ理論のみならず統計物理学や結び目の理論等とも関連をもち、最近注目を集めている。この問題は#P-困難であり、指数オーダーの時間を要するアルゴリズムしか知られていない。本稿では計算の途中に多くの2-同型マイナーが現れることを利用した新しいアルゴリズムを示す。また組合せ論のBell数およびCatalan数を用いてアルゴリズムの計算量の解析をおこなう。このアルゴリズムにより、高々頂点数14かつ辺の数が91であるような任意のグラフ、さらに平面グラフにおいては頂点数144かつ辺の数が264の12×12格子グラフのTutte多項式を標準的なワークステーションにおいて約1時間で計算することができる。
- 社団法人電子情報通信学会の論文
- 1995-07-27
著者
関連論文
- MK-6 東京大学理学部生物情報科学学部教育特別プログラム(大型プロジェクト紹介,学術系企画)
- 線形マトロイド・グラフアレンジメント・半順序での数え上げ問題に対する組合せ的・幾何的アプローチ
- BDDを用いたグラフのTutte多項式計算の再考察
- 量子エントロピーの離散構造
- "Peter Shor : Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing,Vol.26,No.5, pp.1484-1509, 1997 (20世紀の名著名論)
- 5.量子計算と最適化(量子情報処理パラダイム)
- 量子情報処理パラダイム : 1.量子計算の基礎
- Analyzing automorphism groups of oriented matroids by semidefinite programming (Computational Geometry and Discrete Mathematics)
- Computational Analysis of Orientations of Matroids (Computational Geometry and Discrete Mathematics)
- 計算代数的手法を用いた最小費用流の解析 (グレブナ-基底の理論的有効性と実践的有効性)
- 情報処理学会は学会活動でITを活用しているか? : 学術情報発信の観点から(これからの情報処理学会 第3回)
- 絡み目のJones多項式計算の実際
- Dynamic Programming Algorithm for Optimal Double-Base Chains : Extended Abstract (Mathematical Foundations and Applications of Computer Science and Algorithms)
- Tutte多項式とネットワーク信頼性の計算
- Tutte多項式の計算とBDD
- 2分決定グラフ、ガウスの消去法、グラフ理論
- ネットワークシステムの信頼性の定量的評価法 : 枝故障に対する連結性保持の信頼度計算法(ネットワークシステムの危機管理(1))
- グラフのTutte多項式計算システム (新しいパラダイムとしてのアルゴリズム工学)
- Jones多項式の計算
- ネットワーク信頼度計算の実際(信頼性(2))
- ネットワーク信頼度計算に対するモンテカルロ法とBDDを用いた厳密法の計算機実験を通した考察
- Tutte多項式とJones多項式の計算(計算モデルと計算の複雑さに関する研究)
- 有向ネットワーク信頼性のBDDによる計算
- BDDによる計算代数・計算幾何の不変量計算 (アルゴリズムと計算の理論)
- 学会の役割を考える 電子情報通信学会論文誌による国際学術情報発信
- kルートフローのパラメトリック解析に関する考察