Back

神戸大学大学院工学研究科・システム情報学研究科紀要, No. 5, pp. 59-64, 2013
doi:10.5047/gseku.j.2013.002

双方向グラフの最大重み最小帰還辺集合問題について

荒木 徹也1・増田 澄男1・斎藤 寿樹1・山口 一章1

1 工学研究科電気電子工学専攻

(受付:June 26, 2013 受理:August 9, 2013 公開:August 27, 2013)

キーワード: 有向グラフ,アルゴリズム,帰還辺集合,NP 完全,階層グラフ描画

任意の有向グラフをG = (V, E) とする.任意の2 頂点v, wV に対し,(vw) ∈ E であるとき且つそのときに限り(wv) ∈ E であるならば,G を双方向グラフと呼ぶ.本研究では,各辺が非負の重みをもつ双方向グラフG が与えられたときに,その最小帰還辺集合のうち,辺の重みの総和が最大のものを求める問題を考える.この問題は,階層グラフに対して,辺の交差が少ない直交描画を求める問題に応用可能である.本稿では,まず,双方向グラフに対して辺の重みの総和が最大の最小帰還辺集合を求める問題がNP 困難であることを証明する.次に,この問題に対するある発見的手法の有効性を,厳密解法との比較実験により示す.


[Full text] (PDF 512 KB)