Recent developments of electronic devices containing Josephson junctions (JJ) with high-Tc superconductors (HTS) are reported. In particular, the fabrication process and the properties of superconducting quantum interference devices (SQUIDs) with a multilayer structure and ramp-edge-type JJs are described. The JJs were fabricated by recrystallization of an artificially deposited Cu-poor precursory layer. The formation mechanism of the junction barrier is discussed. We have fabricated various types of gradiometers and magnetometers. They have been actually utilized for several application systems, such as a non-destructive evaluation (NDE) system for deep-lying defects in a metallic plate and a reel-to-reel testing system for striated HTS-coated conductors.

The present status of superconducting terahertz emitter using the intrinsic Josephson junctions in high-Tc superconductor Bi2Sr2CaCu2O8+δ is reviewed. Fabrication methods of the emitting device, electrical and optical characteristics of them, synchronizing operation of two emitters and an example of applications to the terahertz imaging will be discussed. After the description of fabrication techniques by an Argon ion milling with photolithography or metal masks and by a focused ion beam, optical properties of radiation spectra, the line width, polarization and the spatial distribution of emission are presented with some discussion on the operation mechanism. For electrical properties, reversible and irreversible operations at high and low electrical currents, respectively, and electrical modulation of the radiation intensity for terahertz imaging are presented.

Let G be a connected graph in which we designate a vertex or a block (a biconnected component) as the center of G. For each cut-vertex v, let Gv be the connected subgraph induced from G by v and the vertices that will be separated from the center by removal of v, where v is designated as the root of Gv. We consider the set R of all such rooted subgraphs in G, and assign an integer, called an index, to each of the subgraphs so that two rooted subgraphs in R receive the same indices if and only if they are isomorphic under the constraint that their roots correspond each other. In this paper, assuming a procedure for computing a signature of each graph in a class of biconnected graphs, we present a framework for computing indices to all rooted subgraphs of a graph G with a center which is composed of biconnected components from . With this framework, we can find indices to all rooted subgraphs of a outerplanar graph with a center in linear time and space.

The k-edge-connectivity augmentation problem with bipartition constraints (kECABP, for short) is defined by “Given an undirected graph G=(V, E) and a bipartition π = {VB, VW} of V with VB ∩ VW = ∅, find an edge set Ef of minimum cardinality, consisting of edges that connect VB and VW, such that G'=(V, E ∪ Ef) is k-edge-connected.” The problem has applications for security of statistical data stored in a cross tabulated table, and so on. In this paper we propose a fast algorithm for finding an optimal solution to (σ + 1)ECABP in O(|V||E| + |V2|log |V|) time when G is σ-edge-connected (σ > 0), and show that the problem can be solved in linear time if σ ∈ {1, 2}.

In an undirected graph, the feedback vertex set (FVS for short) problem is to find a set of vertices of minimum cardinality whose removal makes the graph acyclic. The FVS has applications to several areas such that combinatorial circuit design, synchronous systems, computer systems, VLSI circuits and so on. The FVS problem is known to be NP-hard on general graphs but interesting polynomial solutions have been found for some special classes of graphs. In this paper, we present an O(n2.68 + γn) time algorithm for solving the FVS problem on trapezoid graphs, where γ is the total number of factors included in all maximal cliques.

We describe the fabrication processes and electrical characteristics of two types of NbN junctions. One is a self-shunted NbN/NbNx/AlN/NbN Josephson junction, which is expected to improve the density of integrated circuits; the other is an underdamped NbN/AlNx/NbN tunnel junction with radical-nitride AlNx barriers, which has highly controllable junction characteristics. In the former, the junction characteristics were changed from underdamped to overdamped by varying the thickness of the NbNx layer. Overdamped junctions with a 6-nm-thick NbNx film exhibited a characteristic voltage of Vc = 0.8 mV and a critical current density of Jc = 22 A/cm2 at 4.2 K. In the junctions with radical-nitride AlNx barriers, Jc could be controlled in the range 0.01-3 kA/cm2 by varying the process conditions, and good uniformity of the junction characteristics was obtained.

AC-waveform synthesis with quantum-mechanical accuracy has been attracting many researchers, especially metrologists in national metrology institutes, not only for its scientific interest but its potential benefit to industries. We describe the current status at National Metrology Institute of Japan of development of a Josephson arbitrary waveform synthesizer based on programmable and pulse-driven Josephson junction arrays.

In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.

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.

We investigate connected proper interval graphs without vertex labels. We first give the number of connected proper interval graphs of n vertices. Using this result, a simple algorithm that generates a connected proper interval graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected proper interval graphs is proposed. The algorithm is based on reverse search, and it outputs each connected proper interval graph in (O)1 time.

Hypergraphs drawn in the subset standard are useful to represent group relationships using topographic characteristics such as intersection, exclusion and enclosing. However, they present cluttering when dealing with a moderately high number of nodes (more than 20) and large hyperedges (connecting more than 10 nodes, with three or more overlapping nodes). At this complexity level, a study of the visual encoding of hypergraphs is required in order to reduce cluttering and increase the understanding of larger sets. Here we present a graph model and a visual design that help in the visualization of group relationships represented by hypergraphs. This is done by the use of superimposed visualization layers with different abstraction levels and the help of interaction and navigation through the display.

We present a technology based on Nb/NbxSi1-x/Nb junctions, with barriers near the metal-insulator transition, for applications in superconducting electronics (SCE) as an alternative to Nb/AlOx/Nb tunnel junctions. Josephson junctions with co-sputtered amorphous Nb-Si barriers can be made with a wide variety of electrical properties: critical current density (Jc), capacitance (C), and normal resistance (Rn) can be reliably selected within wide ranges by choosing both the barrier thickness and Nb concentration. Nonhysteretic Nb/NbxSi1-x/Nb junctions with IcRn products greater than 1 mV, where Ic is the critical current, and Jc values near 100 kA/cm2 have been fabricated and are promising for superconductive digital electronics. These barriers have thicknesses of several nanometers; this improves fabrication reproducibility and junction uniformity, both of which are necessary for complex digital circuits. Recent improvements to our deposition system have allowed us to obtain better uniformity across the wafer.

A physical random number generator, which generates truly random number trains by using the randomness of physical phenomena, is widely used in the field of cryptographic applications. We have developed an ultra high-speed superconductive physical random number generator that can generate random numbers at a frequency of more than 10 GHz by utilizing the high-speed operation and high-sensitivity of superconductive integrated circuits. In this study, we have statistically evaluated the quality of the random number trains generated by the superconductive physical random number generator. The performances of the statistical tests were based on a test method provided by National Institute of Standards and Technology (NIST). These statistical tests comprised several fundamental tests that were performed to evaluate the random number trains for their utilization in practical cryptographic applications. We have generated 230 random number trains consisting of 20,000-bits by using the superconductive physical random number generator fabricated by the SRL 2.5 kA/cm2 Nb standard process. The generated random number trains passed all the fundamental statistical tests. This result indicates that the superconductive random number generator can be sufficiently utilized in practical applications.

A single flux quantum (SFQ) logic cell library has been developed for the 10 kA/cm2 Nb multi-layer fabrication process to efficiently design large-scale SFQ digital circuits. In the new cell library, the critical current density of Josephson junctions is increased from 2.5 kA/cm2 to 10 kA/cm2 compared to our conventional cell library, and the McCumber-Stwart parameter of each Josephson junction is increased to 2 in order to increase the circuit operation speed. More than 300 cells have been designed, including fundamental logic cells and wiring cells for passive interconnects. We have measured all cells and confirmed they stably operate with wide operating margins. On-chip high-speed test of the toggle flip-flop (TFF) cell has been performed by measuring the input and output voltages. The TFF cell at the input frequency of up to 400 GHz was confirmed to operate correctly. Also, several fundamental digital circuits, a 4-bit concurrent-flow shift register and a bit-serial adder have been designed using the new cell library, and the correct operations of the circuits have been demonstrated at high clock frequencies of more than 100 GHz.

All MgB2 Josephson junctions with amorphous boron barriers have been fabricated on C-plane sapphire substrates by using a co-evaporation method. The junctions showed Josephson currents and the nonlinear current-voltage characteristics which seem to reflect the superconducting energy gap. The critical current was observed when the thickness of the amorphous boron was in the range of 5 nm to 20 nm. The critical current density was estimated to be 0.4 A/cm2 to 450 A/cm2. By observing he temperature dependence of the critical current we found that the junction had a critical temperature of 10 K and a normal layer in its barrier structure.

Measurement of an individual molar provides rich information for forensic personal identification. We propose a computer-based system for extracting an individual molar from dental panoramic radiographs. A molar is obtained by extracting the region-of-interest, separating the maxilla and mandible, and extracting the boundaries between teeth. The proposed system is almost fully automatic; all that the user has to do is clicking three points on the boundary between the maxilla and the mandible.

A scheduling algorithm aims to minimize the overall execution time of the program by properly allocating and arranging the execution order of the tasks on the core processors such that the precedence constraints among the tasks are preserved. In this paper, we present a new scheduling algorithm by using geometry analysis of the Task Precedence Graph (TPG) based on A* search technique and uses a computationally efficient cost function for guiding the search with reduced complexity and pruning techniques to produce an optimal solution for the allocation/scheduling problem of a parallel application to parallel and multiprocessor architecture. The main goal of this work is to significantly reduce the search space and achieve the optimality or near optimal solution. We implemented the algorithm on general task graph problems that are processed on most of related search work and obtain the optimal scheduling with a small number of states. The proposed algorithm reduced the exhaustive search by at least 50% of search space. The viability and potential of the proposed algorithm is demonstrated by an illustrative example.

A graph is an interval graph if and only if each vertex in the graph can be associated with an interval on the real line such that any two vertices are adjacent in the graph exactly when the corresponding intervals have a nonempty intersection. A number of interesting applications for interval graphs have been found in the literature. In order to find structural features common to structural data which can be represented by intervals, this paper proposes new interval graph structured patterns, called linear interval graph patterns, and a polynomial time algorithm for finding a minimally generalized linear interval graph pattern explaining a given finite set of interval graphs.

The spanning tree problem is to find a tree that connects all the vertices of G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. Klein and Stein demonstrated that a spanning tree can be found in O(log n) time with O(n+m) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. Circular permutation graphs properly contain the set of permutation graphs as a subclass and are first introduced by Rotem and Urrutia. They provided O(n2.376) time recognition algorithm. Circular permutation graphs and their models find several applications in VLSI layout. In this paper, we propose an optimal parallel algorithm for constructing a spanning tree on circular permutation graphs. It runs in O(log n) time with O(n/log n) processors on the EREW PRAM.

Transmission of correlated messages over interference channels with strong interference is considered. As a result, an achievable rate region is presented. It is shown that if the messages are correlated, the achievable rate region can be larger than the capacity region given by Costa and El Gamal. As an example, the Gaussian interference channel is considered.