Method and apparatus for generating n-segment steiner trees
US6389376B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 26, 1999 |
| Grant date | May 14, 2002 |
| Priority date | — |
| Expiry date | Jul 26, 2019 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/30
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The invention is a method and apparatus for generating one or more Steiner trees representing a connection of at least two points. In accordance with an embodiment of the method, a Boolean network function is generated which represents a network of interconnects connecting the at least two points. A binary decision diagram (BDD) for the Boolean network function is generated, the BDD having a root and at least one variable node. The number of vertices for at least one variable node of the BDD is determined. The solution values for one or more of the variables of the Boolean network function are determined in accordance with a path(s) through the BDD from the root to one or more of the variable nodes. In one embodiment, the Boolean network function represents interconnects in an encoded space containing the points to be connected, the interconnects having no greater than “n” segments and arranged to join at a joint. In accordance with this embodiment, the solution values yielded by the BDD path(s) comprise the coordinates of the interconnect joint.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.