2026-03-10T13:40:41Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00231866 2025-01-19T10:37:10Z 1164:2592:11452:11453

二分決定グラフを用いた時間的グラフにおける最短パスの列挙 Enumerating Shortest Paths for Temporal Graphs using Zero-suppressed Binary Decision Diagrams 安藤, 大輝 中畑, 裕 笠原, 正治 Daiki, Ando Yu, Nakahata Shoji, Kasahara ネットワークの頂点の重要性を測る尺度に媒介中心性がある．近年，各辺が時間変化するネットワークの媒介中心性が考えられており，その計算には最短パスの数え上げを要する．そうしたネットワークは時間的グラフによってモデル化され，異なる 4 つ最短の概念とそれに対応する最短パスが定義できる．一方，これらの最短パスの数え上げは多項式時間で列挙できるものもあるが，いくつかは #P 困難に分類される．そこで本研究では，二分決定グラフ（ZDD) を用いた各最短パスの列挙手法を提案する．いくつかのグラフデータに対する計算機実験により，ZDD 構築にかかる時間と解の個数，及び各最短パスを表す ZDD のサイズを比較する． technical report 情報処理学会 2024-01-13 application/pdf 研究報告アルゴリズム（AL） 3 2024-AL-196 1 8 2188-8566 AN1009593X https://ipsj.ixsq.nii.ac.jp/record/231866/files/IPSJ-AL24196003.pdf jpn