WEKO3
アイテム
木幅計算の実用アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/231867
https://ipsj.ixsq.nii.ac.jp/records/231867d7a5f329-6253-49a7-9066-32e434c6389e
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL24196004.pdf (762.7 kB)
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-01-13 | |||||||
| タイトル | ||||||||
| タイトル | 木幅計算の実用アルゴリズム | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 招待講演 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 明治大学 | ||||||||
| 著者名 |
玉木, 久夫
× 玉木, 久夫
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 木幅はグラフアルゴリズムの設計に重要な役割を果たすグラフパラメーターであり，Robertson と Seymour のグラフマイナー理論における中心概念のひとつでもある．グラフ上の計算困難な問題のなかには，木幅をパラメータとして固定パラメータ容易なアルゴリズムを持つ問題が数多く存在する．そのような固定パラメータアルゴリズムを実行するためには，ほとんどの場合まず木幅を計算することが必要となる．木幅を計算する問題は NP 完全であるが，これは実用的な木幅アルゴリズムの開発を断念する理由とはならない．実際，木幅の実用計算をテーマとしたアルゴリズム実装コンテスト PACE2016，PACE2017 を契機として，ここ数年で実用木幅計算の最先端アルゴリズムの性能は飛躍的に向上している．これらの進展の基礎となる理論および技術的なアイディアについて述べ，最新のアルゴリズム [1] について概説する． | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2024-AL-196, 号 4, p. 1-1, 発行日 2024-01-13 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 2188-8566 | |||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
