On Routing Two-Terminal Nets in the Presence of Obstacles.
| dc.contributor.author | JaJa, Joseph F. | en_US |
| dc.contributor.author | Wu, S.A. | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T09:38:24Z | |
| dc.date.available | 2007-05-23T09:38:24Z | |
| dc.date.issued | 1987 | en_US |
| dc.description.abstract | We consider the problem of routing k two-terminal nets in the presence of obstacles in two models: the standard two-layer model and the knock-knee model. Determining routability is known to be NP-complete for arbitrary k. Our main results are polynomial time algorithms to determine whether the given nets are routable in either model for any fixed k. We introduce a technique that reduces the general problem into finding edge-disjoint paths in a graph whose size is proportional to the size of the obstacles. Two optimization criteria are considered: the total length of the wires and the number of vias used. | en_US |
| dc.format.extent | 596819 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/4635 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 1987-127 | en_US |
| dc.title | On Routing Two-Terminal Nets in the Presence of Obstacles. | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1