情報処理学会 第73回全国大会講演要旨

指定された条件を満たすものを全て求める問題は列挙問題と呼ばれる.
列挙問題は様々な分野に応用がある.

グラフGのst-orientationとは,
ある条件を満たすようにGの各辺に方向を付けたものであり,
様々なアルゴリズム中で用いられる.
2連結グラフは任意の2点s,tについてst-orientationを持つことが知られている.

本研究では, 2連結平面グラフGとGの外周の2点sとtが与えられたときに,
Gのst-orientationを全て生成するアルゴリズムを提案する.
アルゴリズムはst-orientationを一つ当たりO(n)時間で列挙する.