グラフの木被服とツア被服問題の近似アルゴリズムについて

スポンサーリンク

概要

論文の詳細を見る
重み付きグラフに関する木被履およびツア被履の問題は,その頂点が頂点被履になっているような最小重みの木およびツアを求める問題であり,いずれもNP困難である.本小文では,これらの問題に対して強多項式時間で定数近似度のアルゴリズムを与える.本アルゴリズムの興味ある特徴は,他の問題,すなわち,重み付き頂点被履問題,行商人問題およびスタイナー木問題の近似算法をうまく組み合わせていることである.
1993-10-01

著者

関連論文

スポンサーリンク