重み制限付き次数3一夕－ミナルシュタイナー木問題に対する近似アルゴリズム

摘要

シュタイナー木問題とは，入力として重み付きグラフGと，Gの頂点の部分集合月が与えられた時，月を全てつなぐ重み最小の木を求める問題である．本研究では，構成されるシュタイナー木に対して｝（i）内部頂点が次数3，（ii）月＝薬頂点の集合，という条件を加えた問題を考えた?まず、この間題がNP困難であることを示した?次に，この間題に対する近似アルゴリズムを2つ提案し，それらのアルゴリズムの近似率を解析した．近似率はそれぞれのアルゴリズムで7／4，25／16となった.