On Two Problems of Nano-PLA Design

Anish Man Singh SHRESTHA  Asahi TAKAOKA  Satoshi TAYU  Shuichi UENO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E94-D   No.1   pp.35-41
Publication Date: 2011/01/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.35
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
biclique problem,  nano-crossbar,  nano-PLA,  orthogonal ray graphs,  subraph isomorphism problem,  

Full Text: PDF>>
Buy this Article




Summary: 
The logic mapping problem and the problem of finding a largest sub-crossbar with no defects in a nano-crossbar with nonprogrammable-crosspoint defects and disconnected-wire defects are 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.