Title :
Orthogonal ray graphs and nano-PLA design
Author :
Shrestha, A.M.S. ; Tayu, Satoshi ; Ueno, Shuichi
Author_Institution :
Dept. of Commun. & Integrated Syst., Tokyo Inst. of Technol., Tokyo, Japan
Abstract :
The logic mapping problem and the problem of finding a largest square sub-crossbar with no defects in a nano-crossbar with nonprogrammable crosspoint defects and disconnected wire defects have been known to be NP-hard. This paper shows that for nano-crossbars with only disconnected wire defects, the former remains NP-hard, while the latter can be solved in polynomial time.
Keywords :
computational complexity; graph theory; logic circuits; nanotechnology; polynomials; wires; NP-hard; disconnected wire defects; logic mapping problem; nano-PLA design; nonprogrammable crosspoint defects; orthogonal ray graphs; polynomial time; Bipartite graph; Logic design; Logic functions; Polynomials; Wire;
Conference_Titel :
Circuits and Systems, 2009. ISCAS 2009. IEEE International Symposium on
Conference_Location :
Taipei
Print_ISBN :
978-1-4244-3827-3
Electronic_ISBN :
978-1-4244-3828-0
DOI :
10.1109/ISCAS.2009.5118416
