An exact rectilinear Steiner tree algorithm
| Autor: | Jeffrey S. Salowe, David M. Warme |
|---|---|
| Rok vydání: | 2002 |
| Předmět: |
Computational complexity theory
Computer science Plane (geometry) Rectilinear Steiner tree Steiner tree problem Set (abstract data type) symbols.namesake Terminal (electronics) TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY symbols Algorithm design Routing (electronic design automation) Algorithm MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | ICCD |
| DOI: | 10.1109/iccd.1993.393331 |
| Popis: | Given a set of terminals in the plane, a rectilinear Steiner minimal tree is a shortest interconnection among these terminals using only horizontal and vertical edges. We present an algorithm that constructs a rectilinear Steiner minimal tree for an input terminal set. On a workstation, problems involving 20 input terminals can be solved in a few seconds, and problems involving 30 input terminals can be solved, on average, in 30 minutes. Previous algorithms could only solve 16 or 17-point problems within the 30-minute time bound. > |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|