The Rectilinear Steiner Arborescence Problem Is NP-Complete
作者： Weiping Shi , Chen Su
DOI: 10.1137/S0097539704371353
关键词:
摘要: Given a set of points in the first quadrant, rectilinear Steiner arborescence (RSA) is directed tree rooted at origin, containing all points, and composed solely horizontal vertical edges oriented from left to right, or bottom top. The complexity finding an RSA with minimum total edge length for general planar point sets has been well-known open problem algorithm design VLSI routing. In this paper, we prove NP-complete strong sense.
sci-hub.se 参考文章(0)