文献

J-GLOBAL ID：201702235853036105   整理番号：17A1078917

グラフのカット幅を求める高速な厳密アルゴリズムの開発

著者 (1件)： 小林靖明 (学習院コンピュータシステム支援組織)
資料名： 学習院大学計算機センター年報  (Annual Report of the Gakushuin University Computer Centre)
巻： 37  ページ： 90-100  発行年： 2017年03月 
JST資料番号： L5808A  ISSN： 0913-4514  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ・現実問題を解くために適用できる,グラフのカット幅を求める(NP困難)厳密アルゴリズムの開発。
・実装を行うアルゴリズム(動的計画法)の擬似コードと,それらの正当性を保証する補題の付与。
・計算機実験による,当該アルゴリズムの実装と,分枝限定法および整数線形計画法の定式化による方法との比較。
・コミットメント補題のみを用いた厳密アルゴリズムが分割統治法を取入れたものよりも実行時間に優れ,分子限定法および整数線形計画法による結果よりも高速に動作することを確認。
・探索アルゴリズムにおいて,初期解や探索ルールの工夫が実行時間や探索空間の削減に有効。

シソーラス用語： *NP困難 ,  *無向グラフ ,  整数線形計画法 ,  厳密解 ,  *高速アルゴリズム ,  分枝限定法 ,  分割統治法 ,  *動的計画法 ,  定式化 ,  計算機シミュレーション ,  木探索 ,  プログラム実行
準シソーラス用語： 厳密アルゴリズム ,  枝刈り【木探索】 ,  計算機実験 ,  実行時間

分類 (2件)： 計算理論  (JB02000A) ,  数理計画法  (KA03030M)

タイトルに関連する用語 (4件)： グラフ ,  カット幅 ,  厳密アルゴリズム ,  開発