An Efficient Rectilinear and Octilinear Steiner Minimal Tree Algorithm for Multidimensional Environments
| Autor: | Ming Che Lee, Chung Chin Luo, Gene Eu Jan |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
General Computer Science
Heuristic (computer science) Computer science Diagonal 0211 other engineering and technologies 02 engineering and technology Minimum spanning tree Steiner tree problem Higher geometry maze routing Set (abstract data type) symbols.namesake Euclidean geometry Hardware_INTEGRATEDCIRCUITS 0202 electrical engineering electronic engineering information engineering General Materials Science Time complexity Steiner tree 021106 design practice & management General Engineering octilinear symbols 020201 artificial intelligence & image processing rectilinear lcsh:Electrical engineering. Electronics. Nuclear engineering Routing (electronic design automation) lcsh:TK1-9971 Algorithm |
| Zdroj: | IEEE Access, Vol 8, Pp 48141-48150 (2020) |
| ISSN: | 2169-3536 |
| Popis: | The rectilinear/octilinear Steiner problem is the problem of connecting a set of terminals $Z$ using orthogonal and diagonal edges with minimum length. This problem has many applications, such as the EDA, VLSI circuit design, fault-tolerant routing in mesh-based broadcast, and Printed Circuit Board (PCB). This paper proposes an obstacle-avoiding 4/8/10/26-directional heuristic algorithm for this problem based on the Areibi’s concept, Higher Geometry Maze Routing, and Sollin’s minimal spanning tree algorithm. The major contributions of this paper are (1) our work is the first report for the octilinear SMTs in the multidimensional environments, (2) we provide an optimal point-to-point routing without any refinement, and (3) the proposed algorithm has higher adaptability to deal with any irregular environment, and can be extended to the $\lambda $ -geometry without any extra work, where $\lambda =2$ , 4, 8 and $\infty $ corresponding to rectilinear, 45°, 22.5° and Euclidean geometries respectively. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|