格子スタイナー木問題に対する領域分割に基づく並列解法

摘要

格子スタイナー木問題とは，各辺に重みを持つ格子グラフH＝(V,E)，障害物，Vの部分集合である指定点集合Pが与えられたとき，Hにおいて障害物を避けて指定点を全て含み，辺重み総和が最小となる木（スタイナー木）を求める問題である．本問題はVLSI基板設計やネットワークルーティングなど幅広い応用を持っが，P＞3でNP－困難であるため様々な近似解法や発見的解法が提案され，計算機実験による性能評価も行われている．本稿は，辺重みが均一な場合における領域分割に基づく近似解法に着目し，高速なアルゴリズムの提案と，比較実験によりその有用性を示すことを目的とする．