抄録
A-032
最小重みの有向部分木アルゴリズムの実験的性能評価
◎安部友輔・千葉英史（法大）
本研究では，各枝に実数の重みを考慮した，連結で閉路を持たない有向グラフを対象とする． そして，このグラフ上で根を指定したときの，最小重み部分木を求めるという問題に取り組む． この問題はNP-困難であるが，以下の場合には簡単に解ける． (1)全ての枝の重みが，非負の場合． (2)全ての枝の重みが，負の場合． (1)の場合は，空木が最適解となり，(2)の場合には，最小重み根指定（全域）有向木問題に帰着され，効率よく解ける方法が知られている． 本研究では，(1)，(2)に当てはまらないような問題に対しても，近似解を求められるアルゴリズムに対して実験的性能評価を行っている．