English  |  正體中文  |  简体中文  |  Items with full text/Total items : 28611/40649
Visitors : 637980      Online Users : 52
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search

Please use this identifier to cite or link to this item: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/25781

Title: A 4-geometry maze router and its application on multiterminal nets
Authors: Gene Eu Jan;Ki-Yin Chang;Su Gao;Ian Parberry
Contributors: NTOU:Department of Merchant Marine
Keywords: Maze router;λ-geometry;cell map;Steiner tree
Date: 2005-01
Issue Date: 2011-10-20T08:32:26Z
Publisher: ACM Transactions on Design Automation of Electronic Systems(TODAES)
Abstract: Abstract:The maze routing problem is to find an optimal path between a given pair of cells on a grid plane. Lee’s algorithm and its variants, probably the most widely used maze routing method, fails to work in the 4-geometry of the grid plane. Our algorithm solves this problem by using a suitable data structure for uniform wave propagation in the 4-geometry, 8-geometry, etc. The algorithm guarantees finding an optimal path if it exists and has linear time and space complexities. Next, to solve the obstacle-avoiding rectilinear and 4-geometry Steiner tree problems, a heuristic algorithm is presented. The algorithm utilizes a cost accumulation scheme based on the maze router to determine the Torricelli vertices (points) for improving the quality of multiterminal nets. Our experimental results show that the algorithm works well in practice. Furthermore, using the 4-geometry router, path lengths can be significantly reduced up to 12% compared to those in the rectilinear router.
Relation: 10(1), pp.116-135
URI: http://ntour.ntou.edu.tw/handle/987654321/25781
Appears in Collections:[商船學系] 期刊論文

Files in This Item:

File Description SizeFormat

All items in NTOUR are protected by copyright, with all rights reserved.


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback