/ プログラム/ 発表一覧/ 著者一覧企業展示一覧/ jsai2015ホーム /

4E1-1 オイラー路の高速な列挙索引化アルゴリズム

*セッションの無断動画配信はご遠慮下さい。

Tweet #jsai2015 このエントリーをはてなブックマークに追加

06月02日(Tue) 09:00〜10:40 E会場(5F北-中講義室 (593))
4E1 「最適化・制約充足」

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