WEKO3
アイテム
頂点被覆数が小さいグラフの最適消去木の計算について
https://ipsj.ixsq.nii.ac.jp/records/145827
https://ipsj.ixsq.nii.ac.jp/records/14582727881250-dfc6-4ba9-b598-6c0e2d71eac2
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL15155010.pdf (262.2 kB)
|
Copyright (c) 2015 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2015-11-13 | |||||||||
| タイトル | ||||||||||
| タイトル | 頂点被覆数が小さいグラフの最適消去木の計算について | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 値 | 学習院大学 | |||||||||
| 著者所属 | ||||||||||
| 値 | 明治大学 | |||||||||
| 著者所属(英) | ||||||||||
| 言語 | en | |||||||||
| 値 | Gakushuin University | |||||||||
| 著者所属(英) | ||||||||||
| 言語 | en | |||||||||
| 値 | Meiji University | |||||||||
| 著者名 |
小林, 靖明
× 小林, 靖明
× 玉木, 久夫
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 無向グラフの消去木の概念は疎行列の分解に対して応用を持つだけでなく，いくつかのグラフ不変量と関係を持つ重要な概念である．無向グラフ G の最適な消去木とは，高さが最小の G の消去木のことであり，一般のグラフにおいて最適な消去木を求める問題は NP 困難である．本稿では，G の頂点被覆数がパラメータとして与えられたときに，最適な消去木を求める問題に対する，多項式サイズのカーネル化と固定パラメータアルゴリズムを与える． | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN1009593X | |||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2015-AL-155, 号 10, p. 1-6, 発行日 2015-11-13 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8566 | |||||||||
| Notice | ||||||||||
| 値 | SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | |||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
