文献

J-GLOBAL ID：201602211411470839   整理番号：16A0041048

頂点被覆数が小さいグラフの最適消去木の計算について

著者 (2件)： 小林靖明 (学習院大) ,  玉木久夫 (明治大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 115  号： 316(MSS2015 20-34)  ページ： 53-58  発行年： 2015年11月13日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 無向グラフの消去木の概念は疎行列の分解に対して応用を持つだけでなく,いくつかのグラフ不変量と関係を持つ重要な概念である。無向グラフGの最適な消去木とは,高さが最小のGの消去木のことであり,一般のグラフにおいて最適な消去木を求める問題はNP困難である。本稿では,Gの頂点被覆数がパラメータとして与えられたときに,最適な消去木を求める問題に対する,多項式サイズのカーネル化と固定パラメータアルゴリズムを与える。(著者抄録)

シソーラス用語： *集合 ,  *最適化問題 ,  無向グラフ ,  スパース行列 ,  不変量 ,  幅 ,  *アルゴリズム ,  グラフ理論
準シソーラス用語： NP困難問題 ,  *カーネル化 ,  疎行列 ,  *多項式時間アルゴリズム ,  単純グラフ ,  *頂点被覆 ,  木幅

分類 (2件)： グラフ理論基礎  (IA02020S) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (5件)： 頂点被覆 ,  グラフ ,  消去 ,  木 ,  計算