A Note on the NP-hardness of the Topological Via Minimization Problem.
| dc.contributor.author | Rim, C.S. | en_US |
| dc.contributor.author | Kashiwabara, Toshinobu | en_US |
| dc.contributor.author | Nakajima, K. | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T09:43:15Z | |
| dc.date.available | 2007-05-23T09:43:15Z | |
| dc.date.issued | 1989 | en_US |
| dc.description.abstract | Suppose that we are given a two-layer routing area bounded by a closed continuous curve B, a set of terminals placed on B which are available on both layers, and a set of two terminal-nets. The topological via minimization problem is the problem of routing the nets by zero-width wires such that no two wires corresponding to different nets intersect on the same layer and the number of vies used is minimized. Very recently, it was reported that this problem is NP-hard but the proof contains a critical flaw. In this paper, we present a correct NP-hardness proof of the problem. | en_US |
| dc.format.extent | 724503 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/4867 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 1989-18 | en_US |
| dc.title | A Note on the NP-hardness of the Topological Via Minimization Problem. | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1