WEKO3
アイテム
DAGに対する幅とアルゴリズムに関する一考察
https://ipsj.ixsq.nii.ac.jp/records/220582
https://ipsj.ixsq.nii.ac.jp/records/220582f2003d99-ffe1-4189-bb47-d4f4f7ece28a
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-Z84-5K-05.pdf (134.5 kB)
|
Copyright (c) 2022 by the Information Processing Society of Japan
|
| Item type | National Convention(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-02-17 | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | DAGに対する幅とアルゴリズムに関する一考察 | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | jpn | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | ソフトウェア科学・工学 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||||||||
| 資源タイプ | conference paper | |||||||||||||
| 著者所属 | ||||||||||||||
| 京大 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 京大 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 京大 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 奈良先端大 | ||||||||||||||
| 著者名 |
森, 順平
× 森, 順平
× 川原, 純
× 湊, 真一
× 笠原, 正治
|
|||||||||||||
| 論文抄録 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | 本研究では非巡回有向グラフ（DAG）に対する幅とアルゴリズムについて考察する。グラフ上の問題について何らかのパラメータを利用してある種の問題を効率的に解く手法は多く研究されているが、DAG上の問題に対して有効なものは多くない。本研究は幅の小さいDAG上の問題を効率的に解くことを目標とする。本研究の貢献は二つに分けられる。一つ目として有向グラフにおける幅を提案する。この幅はそのグラフの有向パスへの近さを表す。無向グラフにおける幅として有名なパス幅の拡張として定義する。二つ目としてDAG上のある種の問題に対して幅が小さいとき効率的に動作するアルゴリズムを設計する。 | |||||||||||||
| 書誌レコードID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AN00349328 | |||||||||||||
| 書誌情報 |
第84回全国大会講演論文集 巻 2022, 号 1, p. 229-230, 発行日 2022-02-17 |
|||||||||||||
| 出版者 | ||||||||||||||
| 言語 | ja | |||||||||||||
| 出版者 | 情報処理学会 | |||||||||||||
