抄録
A-004
区間グラフの向き付けにおける双方向支配
◎原田高浩・荒木　徹（群馬大）
ダイグラフGの頂点の部分集合Sは，Sに含まれない任意の頂点uに対し,(u,v)と(w,u)がGの有向辺であるようなSの頂点u, wを持つなら，SをGの双方向支配集合という．区間グラフとは，頂点集合が数直線上の区間の集合と対応し，かつ2頂点は対応する区間が重なるときに隣接する．
本研究では，区間グラフにサイクルを持たないように各辺に方向付けしたダイグラフに対して，その最小の双方向支配集合を求める多項式時間アルゴリズムを設計した．