• Articles • Previous Articles     Next Articles

A Practical Algorithm for the Minimum Rectilinear Steiner Tree

MA Jun; YANG Bo; MA Shaohan;   

  1. Department of Computer Science; Shandong University; Jinan 250100; P.R. China ;
  • Online:2000-01-10 Published:2000-01-10

An O(n2) time approximation algorithm for the minimum rectilinear Steiner tree is proposed. The approximation ratio of the algorithm is strictlyless than 1.5. The computing performances show the costs of the spanning treesproduced by the algorithm are only 0.8% away from the optimal ones.

Key words: AVS; FFSBM; motion estimation; VLSI;



[1] Hwang F K, Richards D S, Winter P. The Steiner Tree Problem. The Netherlands, North-Holland, 1992, pp.20-200.

[2] Hanan M. On Steiner's problem with rectilinear distance. SIAM J. Applied Math., 1966, 14(5): 255-265.

[3] Synder T L. A simple and faster algorithm for the rectilinear Steiner problem in general dimension. In Prbc. ACM Symp. Computational Geometry, 1990, pp.1340-1345. ……….
[1] Zhi-Feng Xie, Yu-Chen Guo, Shu-Han Zhang, Wen-Jun Zhang, Li-Zhuang Ma. Multi-exposure Motion Estimation based on Deep Convolutional Networks [J]. , 2018, 33(3): 487-501.
[2] Ji-Liang Zhang, Gang Qu, Yong-Qiang Lv, and Qiang Zhou. A Survey on Silicon PUFs and Recent Advances in Ring Oscillator PUFs [J]. , 2014, 29(4): 664-678.
[3] Kai Liu, Ke-Yan Wang, Yun-Song Li, and Cheng-Ke Wu. A Novel VLSI Architecture for Real-Time Line-Based Wavelet Transform Using Lifting Scheme [J]. , 2007, 22(5): 661-672 .
[4] Yi-Ci Cai, Bin Liu, Yan Xiong, Qiang Zhou and Xian-Long Hong. Priority-Based Routing Resource Assignment Considering Crosstalk [J]. , 2006, 21(6): 913-921 .
[5] Jun-Hao Zheng, Lei Deng, Peng Zhang, and Don Xie. An Efficient VLSI Architecture for Motion Compensation of AVS HDTV Decoder [J]. , 2006, 21(3): 370-377 .
[6] Jian-Wen Chen, Guo-Ping Li, and Yun He. A Novel MBAFF Scheme of AVS [J]. , 2006, 21(3): 323-331 .
[7] Ye-Kui Wang. AVS-M: From Standards to Applications [J]. , 2006, 21(3): 332-344 .
[8] Feng Yi, Qi-Chao Sun, Jie Dong, and Lu Yu. Low-Complexity Tools in AVS Part 7 [J]. , 2006, 21(3): 345-353 .
[9] Si-Wei Ma and Wen Gao. Low Complexity Integer Transform and Adaptive Quantization Optimization [J]. , 2006, 21(3): 354-359 .
[10] Tie-Jun Huang and Yong-Liang Liu. Basic Considerations on AVS DRM Architecture [J]. , 2006, 21(3): 366-369 .
[11] Li Zhang Don Xie, and Di Wu. Improved FFSBM Algorithm and Its VLSI Architecture for AVS Video Standard [J]. , 2006, 21(3): 378-382 .
[12] Xin-Fu Wang and De-Bin Zhao. Performance Comparison of AVS and H.264/AVC Video Coding Standards [J]. , 2006, 21(3): 310-314 .
[13] Ji-Gang Wu and Thambipillai Srikanthan. Power Efficient Sub-Array in Reconfigurable VLSI Meshes [J]. , 2005, 20(5): 647-653 .
[14] Dian Zhou[1,2] and Rui-Ming Li[1]. Design and Verification of High-Speed VLSI Physical Design [J]. , 2005, 20(2): 147-165.
[15] J. M. Gallière, M. Renovell, F. Aza?s, and Y. Bertrand. Delay Testing Viability of Gate Oxide Short Defects [J]. , 2005, 20(2): 201-209.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved