抄録
A-005
根付き部分木の総利益最大化
安部友輔・◎古賀裕紀・千葉英史（法大）・斎藤寿樹（神戸大）・影山孝夫・古林　隆・五島洋之（法大）
連結向無グラフ，特別な点，各点の非負収入，各辺の非負コストが与えられたと
き，特別な点を根とする利益最大となるような木を求めたい．ただし，この木は
必ずしも全域である必要はない．本論文では，まず，この問題がNP困難であるこ
とを示し，次に3つの異なるヒューリスティクスを提案する．さらに，整数計画
問題への定式化を行い，CPLEXにより最適値を求め，提案するヒューリスティク
スとの比較を行った．その結果，比較的グラフサイズが小さい場合に，最適値と
一致することが多いことを確認した．