Consider an undirected graph G=(V,E) with n (=|V|) vertices and m (=|E|) edges. It is well-known that the problem of computing the sequence Nn-1,Nn,...,Nm is #P-complete (see e.g.,[3]), where Ni denotes the number of connected spanning subgraphs with i (n-1!im) edges in G. In this paper, by proving new inequalities on the sequence Nn-1,Nn,...,Nm, we show an interesting and stronger property that the sequence γn-1,γn,...,γm, where γi denotes the average number of spanning trees in the connected spanning subgraphs with i edges, is a convex sequence as well as a monotonically increasing sequence, although this property does not hold for the sequence Nn-1,Nn,...,Nm.

Bidirected graphs which are generalizations of undirected graphs, have three types of edges: (+,+)-edges, (-,-)-edges and (+,-)-edges. Undirected graphs are regarded as bidirected graphs whose edges are all of type (+,+). The notion of perfection of undirected graphs can be naturally extended to bidirected graphs in terms of polytopes. The fact that a bidirected graph is perfect if and only if the undirected graph obtained by replacing all edges to (+,+) is perfect was independently proved by several researchers. This paper gives a polyhedral proof of the fact and introduces some new knowledge on perfect bidirected graphs.

The 2-vertex-connectivity augmentation problem for specified vertices (2VCA-SV) is defined as follows: Given an undirected graph G=(V,E), a subgraph G0=(V,E') of G, a specified set of vertices S V and a weight function w:E R^+ (nonnegative real numbers), find a set E" E-E' with the minimum total weight, such that G0+E"=(V,E' E") has at least two internally disjoint paths between any pair of vertices in S. In this paper, we propose an O(|V||E|+ |V|2 log |V|) time algorithm 2-ABIS, whose performance ratio is 2 (3, respectively), for 2VCA-SV if G0 has a connected component containing S (otherwise).

A plane quadrangulation is a plane graph such that each inner face has exactly four edges on its contour. This is a planar dual of a plane graph such that all inner vertices have degree exactly four. A based plane quadrangulation is a plane quadrangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane quadrangulations with at most f faces. The algorithm uses O(f) space and generates such quadrangulations in O(1) time per quadrangulation without duplications. By modifying the algorithm we can generate all biconnected (non-based) plane quadrangulations with at most f faces in O(f3) time per quadrangulation.

A parity check matrix for a binary linear code defines a bipartite graph (Tanner graph) which is isomorphic to a subgraph of a factor graph which explains a mechanism of the iterative decoding based on the sum-product algorithm. It is known that this decoding algorithm well approximates MAP decoding, but degradation of the approximation becomes serious when there exist cycles of short length, especially length 4, in Tanner graph. In this paper, based on the generating idempotents, we propose some methods to design parity check matrices for cyclic codes which define Tanner graphs with no cycles of length 4. We also show numerically error performance of cyclic codes by the iterative decoding implemented on factor graphs derived from the proposed parity check matrices.

For any pair of distinct nodes in an n-pancake graph, we give an algorithm for construction of n-1 internally disjoint paths connecting the nodes in the time complexity of polynomial order of n. The length of each path obtained and the time complexity of the algorithm are estimated theoretically and verified by computer simulation.

This paper reviews the antenna system for Japanese celullar systems and PHS (Personal Handphone System). The unique features of the Japanese cellualr system are multi-band operation, compact diversity antennas, electronic beam tilting, and indoor booster systems. The original antennas for the above purpose will be described. The PHS is also a unique mobile communication system in Japan, and is mainly used for high speed, low cost data transmission. Its original antennas are also presented in this paper.

The capability of a high-temperature superconducting sigma-delta modulator was studied by means of circuit simulation and FFT analysis. Parameters for the circuit simulation were extracted from experimental measurements. The present circuit simulation includes thermal-noise effect. Successive FFT analyses were made to evaluate the dynamic range of the sigma-delta modulator. As a result, the dynamic range was evaluated as 60.1 dB at temperature of 20 K and 56.9 dB at temperature of 77 K.

Analysis of the operation modes of an RF-Field-Driven DC-SQUID (RFDS) is presented. We numerically calculate the current-voltage characteristics (IVC) of the RFDS, where the RF signal is coupled to the SQUID loop magnetically. Under no DC offset flux, the IVC exhibit the enhancement of the even-order steps. We first evaluate the dependence of the maximum 2nd step height of the RFDS upon frequency. Contrary to the results for a single junction, the RFDS maintains its step height at a certain value in the low frequency region. The maintained values of the maximum step height are dependent on βL. The smaller βL is, the larger the maximum step height becomes. Next, we evaluate the dependence of the current positions of the 2nd step upon the amplitude of the RF signal. Under the low frequency condition, the current positions agree with the interference patterns of the SQUID, which means that the operation of the RFDS is based on the quantum transitions in the SQUID loop. Under the high frequency condition, on the other hand, the current positions agree with the results for the single junction, which means that the quantum transitions does not follow the RF signal and that the RFDS behaves like a single junction.

We investigated single flux quantum sinc filters with multistage decimation structure in order to realize high-speed sinc filter operation. Second- and third-order (k=2, 3) sinc filters with a decimation factor N=2 were designed and confirmed their proper operations. These sinc filters with N=2 are utilized as elementary circuit blocks of our multistage decimation sinc filters with N=2M, where M indicates the number of the stage of the decimation. As an example of the multistage decimation filter, we designed a k=2, N=4 sinc filter which was formed from a two-stage decimation structure using k=2, N=2 sinc filters, and confirmed its proper operation. The k=2, N=4 sinc filter consisted of 1372 Josephson junctions with the power consumption of 191 µW.

A software defined radio (SDR) prototype based on a multiprocessor architecture (MPA) is developed. Software for Japanese personal handy phone system (PHS) of a 2G mobile system, and IEEE 802.11 wireless LAN, which has much wider bandwidth than the 2G systems, is successfully implemented. Newly developed flexible-rate pre-/ post-processor (FR-PPP) achieves the flexibility and wideband performance that the platform needs. This paper shows the design of the SDR prototype and evaluates its performance by experiments that include PHS processor load and wireless LAN throughput characteristics and processor load.

This paper describes a novel mobile video monitoring system. The receiver is a PDA (Personal Digital Assistant) with a PHS (Personal Handy Phone system) card. The sender is a PC-based video encoding system, which is connected to an ISDN line by ISDN-TA. Functions such as camera selection, remote camera control and high-resolution snap shot are implemented. In this paper, details of the system are explained and a practicability assessment is performed. An experiment was conducted to measure the upward and downward transmission delay. From the results, the system performs consistently to a theoretical behavior. Furthermore, the performance of this system is quite practical for mobile video monitoring.

A plane drawing of a graph is called a floorplan if every face (including the outer face) is a rectangle. A based floorplan is a floorplan with a designated base line segment on the outer face. In this paper we give a simple algorithm to generate all based floorplans with at most n faces. The algorithm uses O(n) space and generates such floorplans in O(1) time per floorplan without duplications. The algorithm does not output entire floorplans but the difference from the previous floorplan. By modifying the algorithm we can generate without duplications all based floorplans having exactly n faces in O(1) time per floorplan. Also we can generate without duplications all (non-based) floorplans having exactly n faces in O(n) time per floorplan.

Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring problems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H-coloring problem, where H is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n 5.

If there exist any two vertices in G whose distance becomes longer when a vertex u is removed, then u is defined as a hinge vertex. Finding the set of hinge vertices in a graph is useful for identifying critical nodes in an actual network. A number of studies concerning hinge vertices have been made in recent years. In a number of graph problems, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs in O(log n) time with O(n) processors on CREW PRAM for finding all hinge vertices of a trapezoid graph.

In this paper, we review the progress in BiSrCaCuO-2212 Intrinsic Josephson junctions (IJJs) by summarizing our recent results in fabrication and high frequency experiments. Using a double-side fabrication process, a well defined number of intrinsic Josephson junctions in a well defined geometry can be fabricated. The junctions in the stack are quite homogeneous, and the power distribution of external irradiation among the junctions is even. Shapiro steps are clearly observed up to 2.5 THz, and the general condition for the occurrence of Shapiro steps at frequency frf is that it should be much greater than the plasma frequency fpl. Under certain conditions the Shapiro steps are zero-crossing, making some applications possible, such as quantum voltage standard etc.

High-Tc superconductors convincingly showed that these materials are essentially natural arrays of Josephson junctions formed in atomic scale. In this paper, in-plane aligned a-axis-oriented YBa2Cu3O7-δ (YBCO) thin films were successfully grown on LaSrGaO4(LSGO) (100) substrates which were cleaned by ion-beam. Voltage jumps with hysteresis implying intrinsic Josephson effects are observed in c-axis direction. This result suggest that it is possible to achieve planar intrinsic Josephson devices which have applications in high frequency electronics, such as voltage standards, Josephson masers and so on.

We report the measurements on the ramp-edge type Josephson and quasiparticle tunnel junctions with the different interface angle geometry using high-Tc YBa2Cu3O7-y (YBCO) electrodes. The YBCO/I/Ag tunnel junctions with different crystal-interface boundary angles are fabricated for the investigation of zero bias conductance peak. The angle dependent zero bias conductance peak typical to a dx2-y2-wave superconductor is observable. For Josephson junctions, YBCO ramp-edge junctions with different ab-plane electrodes relatively rotated by 45are fabricated using a CeO2 seed-layer technique. The temperature dependence of the maximum Josephson current for YBCO/PBCO/YBCO junctions (PBCO: PrBa2Cu3O7-y) exhibits angle-dependent behavior, qualitatively different from the Ambegaokar-Baratoff prediction. Under microwave irradiation of 9 GHz, the Shapiro steps appear at integer and/or half integer multiples of the voltage satisfying Josephson voltage-frequency relation, whose behavior depends on the sample angle geometry. The results are reasonably interpreted by the dx2-y2-wave theory by taking the zero energy state into account.

The size dependent properties of the intrinsic Josephson junctions in Bi2Sr2CaCu2Oy single crystal mesas in the external magnetic field are studied. The mesas of (1-140) µm long with 7-29 junctions were fabricated and their current-voltage characteristics were measured in external magnetic field applied parallel to the CuO2 layers up to 0.16 T. In zero magnetic field, multiple resistive branches with large hysteresis were observed in the current-voltage characteristics for the fabricated mesas. Almost identical critical currents were also observed for all the junctions in each mesa. With applied magnetic field, Ic of the longer mesas showed a complex magnetic field dependence as compared to that of the short mesas (of about 1 µm in length). It was observed that the lower critical magnetic field of the junctions decreased and approached a constant value with increasing number of junctions and also with increasing length of the junctions. Similar magnetic behavior was obtained by numerical simulations based on coupled sine-Gordon equations for such stacked junctions.

We present measurements of kilohertz and megahertz sine waves synthesized using a Josephson arbitrary waveform synthesizer. A 4.8 kHz sine wave synthesized using an ac-coupled bias technique is shown to have a stable 121 mV peak voltage and harmonic distortion 101 dB below the fundamental (-101 dBc (carrier)). We also present results of our first phase-noise measurement. A 5.0 MHz sine wave was found to have distortion 33 dB lower than the same signal synthesized using a semiconductor digital code generator. The white-noise floor of the Josephson synthesized signal is -132 dBc/Hz and is limited by the noise floor of the preamplifier.