This paper studies the problem of book-embeddings of graphs. When each edge is allowed to appear in one or more pages by crossing the spine of a book, it is well known that every graph G can be embedded in a 3-page book. Recently, it has been shown that there exists a 3-page book embedding of G in which each edge crosses the spine O(log2 n) times. This paper considers a book with more than three pages. In this case, it is known that a complete graph Kn with n vertices can be embedded in a n/2 -page book without any edge-crossings on the spine. Thus it becomes an interesting problem to devise book-embeddings of G so as to reduce both the number of pages used and the number of edge-crossings over the spine. This paper shows that there exists a d-page book embedding of G in which each edge crosses the spine O(logd n) times. As a direct corollary, for any real number s, there is an ns -page book embedding of G in which each edge crosses the spine a constant number of times. In another paper, Enomoto-Miyauchi-Ota show that for an integer d, if n is sufficiently large compared with d, then for any embedding of Kn into a d-page book, there must exist Ω(n2 logd n) points at which edges cross over the spine. This means our result is the best possible for Kn in this case.

All the existing scheduling algorithms order the instructions of the program in such a way that it can be executed in minimal time only for one fixed number of processors. In this paper we propose a new scheduling method, called Parallelism-Independent Scheduling Method, which enables the execution of the scheduled program on parallel computers with any degree of parallelism in near-optimal time. We propose three Parallelism-Independent algorithms, which have the following phases: obtaining a parallel schedule by using a list scheduling heuristics, optimization of the parallel schedule by rearranging the tasks in each level, so that they can be executed efficiently with different degrees of parallelism, serialization of the parallel schedule, and insertion of markers for the parallel execution limits. The three algorithms differ in their optimization phase. To prove the efficiency of our algorithms, we have made simulations with random directed acyclic graphs with different size and degree of parallelism. We compared the results in terms of schedule length to those obtained using the Critical Path Algorithm separately for each degree of parallelism.

A performance comparison between TCP and UDP in PHS Internet access is made by experiment from a media synchronization point of view. We consider a situation where PHS mobile terminals access H. 263 video and G. 726 audio stored at a media server by a streaming method. PIAFS is adopted as the data link protocol for the PHS wireless channels. We examined how white noise and Rayleigh fading on the PHS channel as well as the Internet traffic affect the performance. For the comparison, we evaluated several performance measures such as the coefficient of variation of output interval, and found that UDP outperforms TCP in almost all cases.

The connectivity augmentation problem asks to add to a given graph the smallest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem has been extensively studied, and several efficient algorithm have been discovered. We survey the recent development of the algorithms for this problem. In particular, we show how the minimum cut algorithm due to Nagamochi and Ibaraki is effectively applied to solve the edge-connectivity augmentation problem.

In this paper, we describe our superconducting digital technology that uses Nb/AlOx/Nb Josephson junctions. Superconducting devices have intrinsically superior characteristics than those of semiconductor devices, and Nb/AlOx/Nb junctions have ideal current-voltage characteristics for digital applications. Superconducting devices that use Nb/AlOx/Nb junctions have being actively developed because of their high speed and low power characteristics. Presently, we can fabricate more than twenty thousand junctions on one chip. Using niobium technology, a superconducting 4-kbit RAM has been already successfully developed. We have demonstrated the operation of a network system with a superconducting network chip. Some problems, such as difficulty in high-speed testing, disturbance from trapped magnetic flux and so on, have been overcome by techniques such as a clock-driven testing method, moat structures and so on. The developed technologies, such as the fabrication technology, the design technology for moat structures and so on, must become the basic keys for the development of digital applications based on a single flux quantum device, which will be a promising component for ultra-high speed systems in the twenty-first century.

Recent progress of high-temperature superconductor Josephson junction technology is reviewed in the light of the future application to digital circuits. Among various types of Josephson junctions so far developed, ramp-edge-type junctions with a barrier layer composed of oxide materials in the vicinity of metal-insulator transition seem to offer a unique opportunity to fulfill all the requirements for digital circuit applications by virtue of their small junction dimensions, overdamped properties and relatively high IcRn product values at the temperature of around 30-40 K. Recently developed interface engineered junctions can be classified as junctions of this type. These junctions also raise an interesting problem in physics concerning the possibility of resonant tunneling of Cooper pairs via localized states in the barrier. From the viewpoint of practical applications, the improvement of the spread of the junction parameters is still a serious challenge to the present fabrication technology. Although interface engineered junctions seem to be most promising in this regard at present, 1σ spread of around 8% in the present fabrication technology is far from satisfactory for the fabrication of large-scale integrated circuits. The detailed understanding of the barrier formation mechanism in the interface engineered junction is indispensable not only for advancing this particular fabrication technology but also for improving other junction technology utilizing ramp-edge structures.

It is the purpose of this paper to review the generation of quantized voltage steps in Josephson-junctions, and also the recent practical application of these precise measurements. A 10-V Josephson-junction-array-voltage standard system has been established with a Josephson-junction-array, a phase-locked millimeter wave, and a precise null-detection system. Based on these technologies, the AC Josephson effect has been applied to other precise measurements such as DC error voltage of a multi-integrating analog-to-digital converter and for a pulse-width-modulation type precise voltage calibrator.

This paper proposes a short delay, error-resilient video transmission scheme for mobile radio channels. Compressed video data are sensitive to channel error. Video coding schemes such as H. 263 use variable length coding so channel error can cause synchronization failure in the decoder and fatally degrade the reconstructed video sequence by triggering intra- and inter-frame error propagation. ARQ prevents all forms of error propagation but significantly increases the transmission delay of the video frame. We propose a new error control scheme to reduces the delay incurred by ARQ; the receiving buffer can transmits the video frame data to the video decoder even if not all ARQ frames containing the video frame are received. The encoder transmits additional information, the Macro Block (MB) size, in the video frame header. Upon receiving this information, the receiving buffer can determine MB length which allows MB de-synchronization to be prevented. For example, if an ARQ frame is lost, the decoder determines the position of the missing MB and replace this MB with the equivalent block in the previous video frame; this prevents intra-frame error propagation. When all ARQ frames are received and decoded correctly, the video frame in the reference video memory is replaced with the correctly decoded one. Simulation results show that the proposed scheme can minimize the delay and the reduction in frame rate caused by retransmission control without intra- and inter-error propagation.

Dynamical theory of cellular automata on groups is developed. Main results are non-Euclidean extensions of Sato and Honda's results on the dynamics of Euclidean cellular automata. The notion of the period of a configuration is redefined in a more group theoretical way. The notion of a co-finite configuration substitutes the notion of a periodic configuration, where the new term is given to it to reflect and emphasize the importance of finiteness involved. With these extended or substituted notions, the relations among period preservablity, injectivity, and Poisson stability of parallel maps are established. Residually finite groups are shown to give a nice topological property that co-finite configurations are dense in the configuration space.

By integrating three networks, namely, Public Switched Telephone Network (PSTN), Personal Handy-Phone System (PHS) and Intelligent Network (IN) to work together as a Personal Communication Telephone (PCT) service to be offered in the Bangkok metropolis area, the PCT service enables the advent of three new concepts, first, using the same telephone number as that of the fixed line to become a "Personal Number," second, a cell coverage designed to cover larger areas than that of the PHS (by changing hand-out threshold level from 33 dBµV to 30 dBµV and hand-in threshold level from 30 dBµV to 25 dBµV) in order to reduce the muting time during the handover process and provide higher mobility at up to 60 kilometers per hour, and third, a technique of "2 carriers per area" to reduce "call drop." All these techniques will be described in this paper.

A direct conversion transmitter IC including a proposed frequency doubler, a quadrature modulator, and a 3-bit variable attenuator was fabricated using BiCMOS technology with fT of 12 GHz. This architecture employing frequency doubler is intended for realizing wireless terminals that are low in cost and small in size. The architecture is effective for reducing serious interference between PA and VCO by making the VCO frequency different from that of PA. The proposed frequency doubler comprises a current-driven 90 phase-shifter and an ECL-EXOR circuit for both low power operation and wide input power range of local oscillator (LO). The proposed frequency doubler keeps high output power even when rectangular wave from LO is applied owing to use of the current-driven 90 phase-shifter instead of a voltage-driven 90 phase-shifter. An LO leakage of less than -25 dBc, an image rejection ratio in excess of 45 dBc, and a maximum attenuation of 21 dB were measured. The transmitter IC successfully operates at LO power above -15 dBm and consumes 68 mA from 2.7 V power supply voltage. An active die size is 1.5 mm3 mm.

This paper studies the application of a media synchronization mechanism to the interleaved transmission of video and audio specified by the H.223 Annex in PHS. The media synchronization problem due to network delay jitters in the interleaved transmission has not been discussed in either the Annex or any related standards. The slide control scheme, which has been proposed by the authors, is applied to live media. We also propose a QOS control scheme to control both quality of the media synchronization and that of the transmission delay. Through simulation we confirm the effectiveness of the slide control scheme and the QOS control scheme in the interleaved transmission.

Reducing communication overhead is a key goal of program optimization for current scalable multiprocessors. A well-known approach to achieving this is to map tasks (indivisible units of computation) to processors so that communication and computation overlap as much as possible. In an earlier work, we developed a look-ahead scheduling heuristic for efficiently reducing communication overhead with the aim of decreasing the completion time of a given parallel program. In this paper, we report on an extension of the algorithm, which fills in the idle time slots created by interprocessor communication without increasing the algorithm's time complexity. The results of experiments emphasize the importance of optimally filling idle time slots in processors.

We investigate the basic properties of focused electron beam (FEB)-damaged Josephson junctions on silicon (Si) substrates for high-frequency device applications. YBa2Cu3O7-y (YBCO) Josephson junction arrays were also fabricated by FEB irradiation to confirm the junction uniformity and to investigate their applicability. The junctions exhibit resistively shunted junction (RSJ)-like current-voltage (I-V) curves and the microwave-induced Shapiro steps for all operation temperatures. Two-junction arrays show single-junction-like behavior with the Shapiro steps in an array up to 2 mV. Microwave-induced Shapiro steps correspond to the double voltages Vn=2nVJ, where VJ=f0h/2e in two-junction arrays. The microwave power dependence of I-V curves shows the steps corresponding to the RSJ model.

We have studied the effect of Ga and Ca substitution in the PrBa2Cu3Oδ (PBCO) barrier on the parameters of high-temperature-superconductor ramp-edge Josephson junctions. Pr 1-XCa XBa2Cu3Oδ (X=0. 15, 0. 3) had reduced bulk barrier resistivity as small as 10 mΩcm which was close to the metal-insulator transition. Also, PrBa2Cu 3-ZGa ZOδ, written as GaZ-doped PBCO (Z=0. 15, 0. 3, 0. 6), had enhanced resistivity neater than 1 kΩcm at 4. 2 K. The transport mechanisms in these bulk barriers fitted well with the Mott variable hopping model. The critical current density Jc and normalized junction conductance (R nA)-1 decayed exponentially with almost the same decay length, as the barrier thickness increased. The decay length depended on the barrier material, and ranged from 1. 7 nm to 6. 5 nm for Jc, from 1. 9 nm to 7. 2 nm for (Rn A)-1. Because on these experimental results, we conclude that direct tunneling is the dominant transport mechanism for both quasi particles and paired particles in our junctions, while resonant tunneling should be considered as an additional transport mechanism of these two kinds of particles in the junctions with the PBCO-based barriers reported so far. It was also found that Ga doping raised the characteristic voltage Vc while Ca doping reduced it, though the Vc values obtained here were still small compared to the theoretically predicted values. The spacewise metal insulator transition at the interfaces caused by a high density of localized states in the barriers seemed to be responsible for the reduction in Vc. The best Vc value was 0. 32 mV at 77 K and 5. 2 mV at 4. 2 K using a Ga0. 6-PBCO barrier. These Vc values are suitable for electronics applications. Furthermore, superconducting-gap-like structures were observed in the junctions with highly resistive Ga-doped PBCO barriers.

YBa2Cu3O7-δ co-planar Josephson junctions by Focused Ion Beam were characterized by changing the thickness of YBa2Cu3O7-δ films. The junctions had the thickness dependence of the characteristics. The characteristics were dominantly divided into two types. One had the I-V curve of a flux-flow junction and a weak magnetic response. The other had the I-V curve of RSJ, the IcRn product from 0. 1 mV to 0. 5 mV at 4. 2 K, and a good magnetic response. The critical current density of the junctions increased exponentially with increasing film thickness. From the observation of the junction surface, the junction length was decreased with increasing film thickness by the horizontal growth of the normally grown YBaCuO. In the thicker film (above 240 nm), the microshorts of the normally grown YBaCuO on the abnormally grown YBaCuO area were observed. It is considered that the main part of Josephson current for the junctions changes from the abnormally grown YBaCuO to microshorts when increased with the film thickness.

We describe several properties of very thin stacks of 10 to 20 intrinsic Josephson junctions fabricated on the surface of Bi2Sr2CaCu2O8+δ single crystals. We show that the Joule heating is significantly reduced in these stacks and that the gap structure is clearly observable in the quasiparticle current-voltage (I-V) characteristics. The I-V curves are characterized by a large subgap conductance and a significant gap suppression due to the injection of quasiparticle current. It is found that the IcRn product of these intrinsic Josephson junction stacks is significantly small compared with that expected from the BCS theory. It is also found that there is a tendency that IcRn decreases with increasing c-axis resistivity. Both Ic and the gap voltage exhibit unsaturated temperature dependence at low temperatures. The behavior presents a sharp contrast to that of Josephson junctions made of conventional superconductors. The characteristics are discussed in relation to the d-wave symmetry of the order parameter.

We have studied an in situ edge preparation process and the effect of a substrate rotation during the edge preparation in order to improve the uniformity and electrical characteristics of high-Tc edge-type Josephson junctions. The improved YBa2Cu3Ox/PrBa2Cu3Ox/YBa2Cu3Ox edge junctions showed small 1σ-critical current spreads as low as 10% for 12 junctions. We have confirmed that the spreads do not increase significantly by adding groundplane over the junctions. In this paper, we will describe these processes developed for the fabrication of high-Tc superconducting integrated circuits.

Resonant properties of resistively shunted tunnel junctions dominate the high-frequency performance of Josephson array oscillators. To improve the operating frequency, we have developed resistively shunted Nb/AlOx/Nb tunnel junctions with a small parasitic inductance. The inductance was minimized by reducing the inductive length between the tunnel junction and the contact hole to be about 1µm. By fitting the measured I-V characteristics of the shunted tunnel junction to the simulated characteristics, we estimated the inductance to be about 105 fH. The analysis of resonant properties showed that the shunted tunnel junctions with the small parasitic inductance have a high-frequency performance up to the Nb gap frequency. Josephson array oscillators using 11 such junctions were designed and fabricated to operate at 650 GHz and 1 THz. Shapiro steps induced by Josephson oscillation were clearly observed up to 1 THz. By fitting the step heights to the simulated results, we estimated the output power of the Josephson oscillator delivered to the load resistor to be about 10 µW at 625 GHz and 50 nW at 1 THz.

We present two types of ICF (INHIBIT Controlled by Fluxon) gates as the basic circuits of the phase-mode logic family, and fabricate an adder circuit. The experimental result demonstrates that the carry operation followed up to 99 GHz input pulses. The performance of Josephson devices is improved by the use of junctions with high current density (Jc). We may use the high-Jc junctions without external resistive shunt in the phase-mode logic circuits because of reduction of the junction hysteresis. One of the ways to overcome the large area occupancy for geometric inductance is to utilize the effective inductance of a Josephson junction itself. We investigate a circuit construction with high-Jc inductor junctions, intrinsically overdumped junctions and junction-type resistors for the compactness of circuit integration, and discuss various aspects of the circuit construction.