@techreport{oai:ipsj.ixsq.nii.ac.jp:00031997,
 author = {加藤亮 and 今井, 桂子 and 浅野, 孝夫 and Ryo, Kato and Keiko, Imai and Takao, Asano},
 issue = {7(2001-AL-082)},
 month = {Jan},
 note = {平面上に与えられたn個の点集合Sに対して、どの２点間にも２点間のL1-距離に等しい長さのパスが存在するネットワークをSのマンハッタンネットワークという．最小マンハッタンネットワーク問題は、このようなネットワークのうちで、辺の長さの総和（辺長和）が最小となるものを求める問題である．現在、この問題に対して最適解を求める多項式時間のアルゴリズムは知れておらず、既知の(多項式時間）近似アルゴリズムの最良の近似精度は4である．本論文では、この問題に対する２近似アルゴリズムを提案する。, For a given set S of n points in the plane, a manhattan network for S is a network in which,for each pair of points in S, there is a path between them of length equal to their L1-distance. The minimum manhattan network problem is a problem of finding a manhattan network of minimum length. For this problem, no polynomial time exact algorithm has been known and a 4 approximation algorithm has been proposed. In this paper, we improve this bound and present a 2 approximation algorithm.},
 title = {最小マンハッタンネットワーク問題に対する近似アルゴリズム},
 year = {2002}
}