| Item type |
SIG Technical Reports(1) |
| 公開日 |
2024-01-13 |
| タイトル |
|
|
タイトル |
二分決定グラフを用いた時間的グラフにおける最短パスの列挙 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Enumerating Shortest Paths for Temporal Graphs using Zero-suppressed Binary Decision Diagrams |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
奈良先端科学技術大学院大学先端科学技術研究科 |
| 著者所属 |
|
|
|
奈良先端科学技術大学院大学先端科学技術研究科 |
| 著者所属 |
|
|
|
奈良先端科学技術大学院大学先端科学技術研究科 |
| 著者所属(英) |
|
|
|
en |
|
|
Nara Institute of Science and Technology, Graduate School of Science and Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Nara Institute of Science and Technology, Graduate School of Science and Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Nara Institute of Science and Technology, Graduate School of Science and Technology |
| 著者名 |
安藤, 大輝
中畑, 裕
笠原, 正治
|
| 著者名(英) |
Daiki, Ando
Yu, Nakahata
Shoji, Kasahara
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
ネットワークの頂点の重要性を測る尺度に媒介中心性がある．近年，各辺が時間変化するネットワークの媒介中心性が考えられており，その計算には最短パスの数え上げを要する．そうしたネットワークは時間的グラフによってモデル化され，異なる 4 つ最短の概念とそれに対応する最短パスが定義できる．一方，これらの最短パスの数え上げは多項式時間で列挙できるものもあるが，いくつかは #P 困難に分類される．そこで本研究では，二分決定グラフ（ZDD) を用いた各最短パスの列挙手法を提案する．いくつかのグラフデータに対する計算機実験により，ZDD 構築にかかる時間と解の個数，及び各最短パスを表す ZDD のサイズを比較する． |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2024-AL-196,
号 3,
p. 1-8,
発行日 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 |
|
出版者 |
情報処理学会 |
IPSJ-AL24196003.pdf (1.2 MB)
