A Note on the NP-hardness of the Topological Via Minimization Problem.

Simple item page
dc.contributor.authorRim, C.S.en_US
dc.contributor.authorKashiwabara, Toshinobuen_US
dc.contributor.authorNakajima, K.en_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:43:15Z
dc.date.available2007-05-23T09:43:15Z
dc.date.issued1989en_US
dc.description.abstractSuppose 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.extent724503 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/4867
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1989-18en_US
dc.titleA Note on the NP-hardness of the Topological Via Minimization Problem.en_US
dc.typeTechnical Reporten_US

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_89-18.pdf
Size:
707.52 KB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports