数理情報工学／ 2021 SPQR木を用いたオイラー路の数え上げ

研究概要

無向グラフに対するオイラー路の数え上げは#P-completeであることが知られている. SPQR木というデータ構造を利用し, 対象となる2-連結グラフの3-連結成分のサイズが小さい場合に高速なアルゴリズムを提案した.

思うように進まない期間もありましたが, 何とか形にすることができました. 定兼先生をはじめとした研究室の方々に感謝します.