Luby et al. derived evolution of degree distributions in residual graphs for irregular LDPC code ensembles. Evolution of degree distributions in residual graphs is important characteristic which is used for finite-length analysis of the expected block and bit error probability over the binary erasure channel. In this paper, we derive detailed evolution of degree distributions in residual graphs for irregular LDPC code ensembles with joint degree distributions.

Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical power demand problem, computer network design, circuit analysis, etc. An optimal parallel algorithm for finding a spanning tree on the trapezoid graph is given by Bera et al., it takes O(log n) time with O(n/log n) processors on the EREW (Exclusive-Read Exclusive-Write) PRAM. Bera et al.'s algorithm is very simple and elegant. Moreover, it can correctly construct a spanning tree when the graph is connected. However, their algorithm can not accept a disconnected graph as an input. Applying their algorithm to a disconnected graph, Concurrent-Write occurs once for each connected component, thus this can not be achieved on EREW PRAM. In this paper we present an O(log n) time parallel algorithm with O(n/log n) processors for constructing a spanning forest on trapezoid graph G on EREW PRAM even if G is a disconnected graph.

Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between two arbitrary nodes in time bounded by a polynomial in n, the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of the path lengths after proving the correctness of the algorithm. In addition, we report the results of computer experiments evaluating the average performance of the algorithm.

The subject of this paper is maximum weight matchings of graphs. An edge set M of a given graph G is called a matching if and only if any pair of edges in M share no endvertices. A maximum weight matching is a matching whose total weight (total sum of edge-weights) is maximum among those of G. The maximum weight matching problem (MWM for short) is to find a maximum weight matching of a given graph. Polynomial algorithms for finding an optimum solution to MWM have already been proposed: for example, an O(|V|4) time algorithm proposed by J. Edmonds, and an O(|E||V|log |V|) time algorithm proposed by H.N. Gabow. Some applications require obtaining a matching of large total weight (not necessarily a maximum one) in realistic computing time. These existing algorithms, however, spend extremely long computing time as the size of a given graph becomes large, and several fast approximation algorithms for MWM have been proposed. In this paper, we propose six approximation algorithms GRS+, GRS_F+, GRS_R+, GRS_S+, LAM_a+ and LAM_as+. They are enhanced from known approximation ones by adding some postprocessings that consist of improved search of weight augmenting paths. Their performance is evaluated through results of computing experiment.

We developed an Nb-based fabrication process for single flux quantum (SFQ) circuits in a Japanese government project that began in September 2002 and ended in March 2007. Our conventional process, called the Standard Process (SDP), was improved by overhauling all the process steps and routine process checks for all wafers. Wafer yield with the improved SDP dramatically increased from 50% to over 90%. We also developed a new fabrication process for SFQ circuits, called the Advanced Process (ADP). The specifications for ADP are nine planarized Nb layers, a minimum Josephson junction (JJ) size of 11 µm, a line width of 0.8 µm, a JJ critical current density of 10 kA/cm2, a 2.4 Ω Mo sheet resistance, and vertically stacked superconductive contact holes. We fabricated an eight-bit SFQ shift register, a one million SQUID array and a 16-kbit RAM by using the ADP. The shift register was operated up to 120 GHz and no short or open circuits were detected in the one million SQUID array. We confirmed correct memory operations by the 16-kbit RAM and a 5.7 times greater integration level compared to that possible with the SDP.

Longest path problem is a problem for finding a longest path in a given graph. While the graph classes in which the Hamiltonian path problem can be solved efficiently are widely investigated, there are few known graph classes such that the longest path problem can be solved efficiently. Polynomial time algorithms for finding a longest cycle and a longest path in a Ptolemaic graph are proposed. Ptolemaic graphs are the graphs that satisfy the Ptolemy inequality, and they are the intersection of chordal graphs and distance-hereditary graphs. The algorithms use the dynamic programming technique on a laminar structure of cliques, which is a recent characterization of Ptolemaic graphs.

Consider an undirected multigraph G=(V,E) with n vertices and m edges, and let Ni denote the number of connected spanning subgraphs with i(min) edges in G. Recently, we showed in [3] the validity of (m-i+1)Ni-1>Ni for a simple graph and each i(min). Note that, from this inequality, 2 is easily derived. In this paper, for a multigraph G and all i(min), we prove (m-i+1)Ni-1(i-n+2)Ni, and give a necessary and sufficient condition by which (m-i+1)Ni-1=(i-n+2)Ni. In particular, this means that (m-i+1)Ni-1>Ni is not valid for all multigraphs, in general. Furthermore, we prove 2, which is not straightforwardly derived from (m-i+1)Ni-1(i-n+2)Ni, and also introduce a necessary and sufficent condition by which =2. Moreover, we show a sufficient condition for a multigraph to have Nn2>Nn-1Nn+1. As special cases of the sufficient condition, we show that if G contains at least +1 multiple edges between some pair of vertices, or if its underlying simple graph has no cycle with length more than 4, then Nn2>Nn-1Nn+1.

Let G =(V, E) be an undirected simple graph with u ∈ V. 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/log n) processors on EREW PRAM for finding all hinge vertices of a circular-arc graph.

This paper deals with a universal coding problem for a certain kind of multiterminal source coding system that we call the complementary delivery coding system. In this system, messages from two correlated sources are jointly encoded, and each decoder has access to one of the two messages to enable it to reproduce the other message. Both fixed-to-fixed length and fixed-to-variable length lossless coding schemes are considered. Explicit constructions of universal codes and bounds of the error probabilities are clarified via type-theoretical and graph-theoretical analyses.

A measurement system is developed to observe the switching current distribution in Bi2Sr2CaCu2O8+δ intrinsic Josephson junctions (IJJ's). We have designed the frequency responses of filters and cables to achieve the compatibility of sufficient isolation at high frequency region and accurate detection of the distribution at low frequency region. The temperature dependence of the switching current distributions measured on a IJJ by the present system agrees well with the theoretical calculation in the temperature range from 70 mK to 5 K. The consistency of the crossover temperature between experimental result and calculation suggests that the designed measurement system succeeded in observing the macroscopic quantum tunneling process.

The utilization of a high-Tc superconductor for implementing a superconducting qubit is to be expected. Recent researches on the quantum property of Josephson junctions in high-Tc superconductors indicate that the low energy quasiparticle excitation is weak enough to observe the macroscopic quantum tunneling. Therefore, a detailed study on the quantum property of high-Tc Josephson junctions becomes more important for applications. We show our experimental results of the macroscopic tunneling of current biased intrinsic Josephson junctions in Bi-2212 and its resonant activation in the presence of microwave radiation.

Development of ultrafast optical interfaces that can operate in sub-terahertz region is important to apply superconducting electronic devices to the high-end systems. We have performed several fundamental researches to realize the ultrafast optical input interface for superconducting electronic devices. Firstly, we observed optical response of amorphous Ge thin films, and the results indicated that an amorphous Ge photoconductive switch could stably operate in a terahertz frequency range as an optical-to-electrical signal converter in the low-temperature region below Tc of YBCO. Next, we have fabricated optical-to-electrical signal conversion system with photomixing technique, and we have demonstrated the generation and the detection of high frequency signals over 50 GHz. Finally, we have observed optical responses of a Josephson vortex flow transistor under irradiation of femtosecond laser pulses, and the results suggeste that the device has high potential as an optical interface.

In this paper, we propose an algorithm that solves the node-to-node disjoint paths problem in n-burnt pancake graphs in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n3) and the maximum path length 3n+4. We conducted a computer experiment for n=2 to 100 to measure the average performance of our algorithm. The results show that the average time complexity is O(n3.0) and the maximum path length is 3n+4.

In this paper, we give an algorithm for the node-to-set disjoint paths problem in a transposition graph. The algorithm is of polynomial order of n for an n-transposition graph. It is based on recursion and divided into two cases according to the distribution of destination nodes. The maximum length of each path and the time complexity of the algorithm are estimated theoretically to be O(n7) and 3n - 5, respectively, and the average performance is evaluated based on computer experiments.

A plane drawing of a plane graph is called a rectangular drawing if every face including the outer face is a rectangle. A based rectangular drawing is a rectangular drawing with a designated base line segment on the outer face. An algorithm to generate all based rectangular drawings having exactly n faces is known. The algorithm generates each based rectangular drawing having exactly n faces in constant time "on average." In this paper, we give another simple algorithm to generate all based rectangular drawings having exactly n faces. Our algorithm generates each based rectangular drawing having exactly n faces in constant time "in the worst case." Our algorithm generates each based rectangular drawing so that it can be obtained from the preceding one by at most three operations and does not output entire drawings but the difference from the preceding one. Therefore the derived sequence of based rectangular drawings is a kind of combinatorial Gray code for based rectangular drawings.

A naive coding of floorplans needs 2m bits for each floorplan. In this paper we give a new simple coding of floorplans, which needs only 5m/3 bits for each floorplan.

In this paper, we study the feedback vertex set problem for trivalent Cayley graphs, and construct a minimum feedback vertex set in trivalent Cayley graphs using the result on cube-connected cycles and the Cayley graph representation of trivalent Cayley graphs.

Let G = (D ∪ S,E) be an undirected graph with a vertex set D ∪ S and an (undirected) edge set E, where the vertex set is partitioned into two subsets, a demand vertex set D and a supply vertex set S. We assume that D ≠ and S ≠ in this paper. Each demand or supply vertex v has a positive real number d(v) or s(v), called the demand or supply of v, respectively. For any subset V' ⊆ D ∪ S, the demand of V' is defined by d(V') = Σv∈V'∩Dd(v) if V' ∩ D ≠ or d(V') = 0 if V' ∩ D = . Let s(S) = Σv∈S s(v). Any partition π = {V1,..., Vr} (|S| r |D ∪ S|) of D ∪ S is called a feasible partition of G if and only if π satisfies the following (1) and (2) for any k = 1,..., r: (1) |Vk ∩ S|1, and (2) if Vk ∩ S = {uk} then the induced subgraph G[Vk] of G is connected and d(Vk)s(uk). The demand d(π) of π is defined by d(π)=d(Vk). The "Maximum-Supply Partitioning Problem (MSPP)" is to find a feasible partition π of G such that d(π) is maximum among all feasible partitions of G. We implemented not only existing algorithms for obtainity heuristic or optimum solutions to MSPP but also those that are corrected or improved from existing ones. In this paper we show comparison of their capability based on computational experiments.

The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V,E), a specified set of vertices S ⊆V and a function g: V → Z+ ∪{∞}, find a smallest set E' of edges such that (V,E ∪ E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any v ∈ V, E' includes at most g(v) edges incident to v, where Z+ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.

This paper presents a fast switching CMOS frequency synthesizer with a new coarse tuning method for PHS applications. To achieve the fast lock-time and the low phase noise performance, an efficient bandwidth control scheme is proposed. To change the bandwidth, the charge pump current and the loop filter zero resistor should be changed. Charge pump up/down current mismatches are compensated with the current mismatch compensation block. The proposed coarse tuning method selects the optimal tuning capacitances of the LC-VCO to optimize the phase noise and the lock-time. The measured lock-time is about 20 µs and the phase noise is -121 dBc/ at 600 kHz offset. This chip is fabricated with 0.25 µm CMOS technology, and the die area is 0.7 mm2.1mm. The power consumption is 54 mW at 2.7 V supply voltage.