SPQR木を用いたオイラー路の数え上げ

川向 聡

（指導教員：定兼 邦彦 教授／数理情報第2研究室）

研究概要

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

SPQR木を用いた数え上げの過程

卒論の感想

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