The Rectilinear Steiner Arborescence Problem Is NP-Complete Academic Article

abstract

• Given a set of points in the first quadrant, a rectilinear Steiner arborescence (RSA) is a directed tree rooted at the origin, containing all points, and composed solely of horizontal and vertical edges oriented from left to right, or from bottom to top. The complexity of finding an RSA with the minimum total edge length for general planar point sets has been a well-known open problem in algorithm design and VLSI routing. In this paper, we prove the problem is NP-complete in the strong sense. 2006 Society for Industrial and Applied Mathematics.

authors

• Shi, Weiping

published proceedings

• SIAM Journal on Computing

author list (cited authors)

• Shi, W., & Su, C.

citation count

• 45

complete list of authors

• Shi, Weiping||Su, Chen

publication date

• January 2005

publisher

• Society for Industrial & Applied Mathematics (SIAM)  Publisher

published in

• SIAM Journal on Computing  Journal

Digital Object Identifier (DOI)

• 10.1137/s0097539704371353

URI

• https://hdl.handle.net/1969.1/182684

start page

• 729

end page

• 740

volume

• 35

issue

• 3

URL

• http://dx.doi.org/10.1137/s0097539704371353