US Patent 7254799 - Nanowire crossbar optimization using graph theory

http://www.freepatentsonline.com/7254799.html

Nanoscale crossbars are a leading contender for a breakthrough platform for nanoelectronics and has a variety of potential advantages in addition to scaling such as reduced manufacturing cost and the capability of reconfigurability. However there are also some drawbacks including a relatively large percentage of defects. This patent from Hewlett-Packard teaches using graph theory to effectively allocate the working crosspoints. Claim 1 reads:

1. A method for allocating nanowire junctions in a nanowire crossbar, the method comprising: receiving a circuit; receiving a nanowire crossbar having one or more randomly distributed non-functional nanowire junctions; constructing a circuit graph based on the circuit; constructing a crossbar graph based on the nanowire crossbar; searching for a graph monomorphism based on the circuit graph and the crossbar graph; and allocating nanowire junctions of the nanowire crossbar based on the graph monomorphism.