Two-level rectilinear Steiner trees

详细信息    查看全文

• 作者：Stephan Held^a ; ^{held@or.uni-bonn.de}Author Vitae ; Nicolas Kä ; mmerling^b ; ^{kaemmerling@itl.tu-dortmund.de}Author Vitae
• 关键词：Steiner trees ; Approximation algorithms ; VLSI design
• 刊名：Computational Geometry
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：61
• 期：Complete
• 页码：48-59
• 全文大小：477 K
• 卷排序：61

文摘

Given a set P of terminals in the plane and a partition of P into k   subsets P1,…,PkP1,…,Pk, a two-level rectilinear Steiner tree consists of a rectilinear Steiner tree TiTi connecting the terminals in each set PiPi (i=1,…,ki=1,…,k) and a top-level tree TtopTtop connecting the trees T1,…,TkT1,…,Tk. The goal is to minimize the total length of all trees. This problem arises naturally in the design of low-power physical implementations of parity functions on a computer chip.For bounded k we present a polynomial time approximation scheme (PTAS) that is based on Arora's PTAS for rectilinear Steiner trees after lifting each partition into an extra dimension.For the general case we propose an algorithm that predetermines a connection point for each TiTi and TtopTtop (i=1,…,ki=1,…,k). Then, we apply any approximation algorithm for minimum rectilinear Steiner trees in the plane to compute each TiTi and TtopTtop independently.This gives us a 2.37-factor approximation with a running time of O(|P|log⁡|P|)O(|P|log⁡|P|) suitable for fast practical computations. The approximation factor reduces to 1.63 by applying Arora's approximation scheme in the plane.