Search

A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o−1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least n−1 in G. A block-chain is a graph whose block graph is a path, i.e., it is either a P1, P2, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks. Obviously, every traceable graph is a block-chain, but the reverse does not hold. In this paper we characterize all the pairs of connected o−1-heavy graphs that guarantee traceability of block-chains. Our main result is a common extension of earlier work on degree sum conditions, forbidden subgraph conditions and heavy subgraph conditions for traceability

Many nanoscale devices require precise optimization to function. Tuning them to the desired operation regime becomes increasingly difficult and time-consuming when the number of terminals and couplings grows. Imperfections and device-to-device variations hinder optimization that uses physics-based models. Deep neural networks (DNNs) can model various complex physical phenomena but, so far, are mainly used as predictive tools. Here, we propose a generic deep-learning approach to efficiently optimize complex, multi-terminal nanoelectronic devices for desired functionality. We demonstrate our approach for realizing functionality in a disordered network of dopant atoms in silicon. We model the input-output characteristics of the device with a DNN, and subsequently optimize control parameters in the DNN model through gradient descent to realize various classification tasks. When the corresponding control settings are applied to the physical device, the resulting functionality is as predicted by the DNN model. We expect our approach to contribute to fast, in situ optimization of complex (quantum) nanoelectronic devices.

Classification is an important task at which both biological and artificial neural networks excel 1,2 . In machine learning, nonlinear projection into a high-dimensional feature space can make data linearly separable 3,4 , simplifying the classification of complex features. Such nonlinear projections are computationally expensive in conventional computers. A promising approach is to exploit physical materials systems that perform this nonlinear projection intrinsically, because of their high computational density 5 , inherent parallelism and energy efficiency 6,7 . However, existing approaches either rely on the systems' time dynamics, which requires sequential data processing and therefore hinders parallel computation 5,6,8 , or employ large materials systems that are difficult to scale up 7 . Here we use a parallel, nanoscale approach inspired by filters in the brain 1 and artificial neural networks 2 to perform nonlinear classification and feature extraction. We exploit the nonlinearity of hopping conduction 9-11 through an electrically tunable network of boron dopant atoms in silicon, reconfiguring the network through artificial evolution to realize different computational functions. We first solve the canonical two-input binary classification problem, realizing all Boolean logic gates 12 up to room temperature, demonstrating nonlinear classification with the nanomaterial system. We then evolve our dopant network to realize feature filters 2 that can perform four-input binary classification on the Modified National Institute of Standards and Technology handwritten digit database. Implementation of our material-based filters substantially improves the classification accuracy over that of a linear classifier directly applied to the original data 13 . Our results establish a paradigm of silicon-based electronics for small-footprint and energy-efficient computation 14 .