Polynomial Time Approximation Scheme for the Rectilinear Steiner Arborescence Problem

Bing Lu () and Lu Ruan ()
Additional contact information
Bing Lu: University of Minnesota
Lu Ruan: University of Minnesota

Journal of Combinatorial Optimization, 2000, vol. 4, issue 3, No 4, 357-363

Abstract: Abstract Given a set N of n terminals in the first quadrant of the Euclidean plane E 2, find a minimum length directed tree rooted at the origin o, connecting to all terminals in N, and consisting of only horizontal and vertical arcs oriented from left to right or from bottom to top. This problem is called rectilinear Steiner arborescence problem, which has been proved to be NP-complete recently (Shi and Su, 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2000, to appear). In this paper, we present a polynomial time approximation scheme for this problem.

Keywords: PTAS; arborescence; Steiner terminals; VLSI design; approximation algorithm (search for similar items in EconPapers)
Date: 2000
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009826311973 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:4:y:2000:i:3:d:10.1023_a:1009826311973

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009826311973

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().