06月02日(Tue) 09:00〜10:40 E会場(5F北-中講義室 (593))
演題番号 | 4E1-1 |
---|---|
題目 | オイラー路の高速な列挙索引化アルゴリズム |
著者 | ムハマド ホリルロハマン(北海道大学大学院情報科学研究科) 湊 真一(北海道大学 大学院 情報科学研究科) |
時間 | 06月02日(Tue) 09:00〜09:20 |
概要 | 与えられたグラフのオイラー路を高速に列挙索引化するアルゴリズムを提案する。このアルゴリズムは、KnuthのSimpath法を拡張したもので、有向非巡回グラフ(DAG)を用いて各辺の接続関係を圧縮して表現することにより、高速な計算を実現した。本手法により、膨大な個数のオイラー路を、現実的な時間で正確に数え上げることが可能となった。 |
論文 | PDFファイル |