Canonical decomposition for bipartite graphs, which was introduced by Fouquet, Giakoumakis, and Vanherpe (1999), is a decomposition scheme for bipartite graphs associated with modular decomposition. Weak-bisplit graphs are bipartite graphs totally decomposable (i.e., reducible to single vertices) by canonical decomposition. Canonical decomposition comprises series, parallel, and K+S decomposition. This paper studies a decomposition scheme comprising only parallel and K+S decomposition. We show that bipartite graphs totally decomposable by this decomposition are precisely P6-free chordal bipartite graphs. This characterization indicates that P6-free chordal bipartite graphs can be recognized in linear time using the recognition algorithm for weak-bisplit graphs presented by Giakoumakis and Vanherpe (2003).

Our group has developed terahertz(THz)-waves emitting devices utilizing single crystals of high temperature superconductor Bi2Sr2CaCu2O8+δ (Bi2212). The working principle of the device is based on the AC Josephson effect which is originated in the intrinsic Josephson junctions (IJJs) constructed in Bi2212 single crystals. In principle, based on the superconducting gap of the compound and the AC Josephson effect, the emission frequency range from 0.1 to 15 THz can be generated by simply adjusting bias voltages to the IJJs. In order to improve the device performances, we have performed continuous improvement to the device structures. In this paper, we present our recent approaches to high performance Bi2212 THz-waves emitters. Firstly, approaches to the reduction of self Joule heating of the devices is described. In virtue of improved device structures using Bi2212 crystal chips, the device characteristics, such as the radiation frequency and the output power, become better than previous structures. Secondly, developments of THz-waves emitting devices using IJJs-mesas coupled with external structures are explained. The results clearly indicate that the external structures are very useful not only to obtain desired radiation frequencies higher than 1 THz but also to control radiation frequency characteristics. Finally, approaches to further understanding of the spontaneous synchronization of IJJs is presented. The device characteristics obtained through the approaches would play important roles in future developments of THz-waves emitting devices by use of Bi2212 single crystals.

Studies on intrinsic Josephson junctions (IJJs) of cuprate superconductors are reviewed. A system consisting of a few IJJs provides phenomena to test the Josephson phase dynamics and its interaction between adjacent IJJs within a nanometer scale, which is unique to cuprate superconductors. Quasiparticle density of states, which provides direct information on the Cooper-pair formation, is also revealed in the system. In contrast, Josephson plasma emission, which is an electromagnetic wave radiation in the sub-terahertz frequency range from an IJJ stack, arises from the synchronous phase dynamics of hundreds of IJJs coupled globally. This review summarizes a wide range of physical phenomena in IJJ systems having capacitive and inductive couplings with different nanometer and micrometer length scales, respectively.

Direct-current superconducting quantum interference device (dc-SQUID) based on intrinsic Josephson junction (IJJ) has been fabricated using Bi2Sr2CaCu2O8+δ (Bi-2212) films grown on MgO substrates with surface steps. The superconducting loop parallel to the film surface across the step edge contains two IJJ stacks along the edge. The number of crystallographically stacked IJJ for each SQUIDs were 40, 18 and 3. Those IJJ SQUIDs except for one with 40 stacked IJJs revealed clear periodic modulation of the critical current for the flux quanta through the loops. It is anticipated that phase locking of IJJ has an effect on the modulation depth of the IJJ dc-SQUID.

Intrinsic Josephson junctions (IJJs) in the high-Tc cuprate superconductors have several fascinating properties, which are superior to the usual Josephson junctions obtained from conventional superconductors with low Tc, as follows; (1) a very thin thickness of the superconducting layers, (2) a strong interaction between junctions since neighboring junctions are closely connected in an atomic scale, (3) a clean interface between the superconducting and insulating layers, realized in a single crystal with few disorders. These unique properties of IJJs can enlarge the applicable areas of the superconducting qubits, not only the increase of qubit-operation temperature but the novel application of qubits including the macroscopic quantum states with internal degree of freedom. I present a comprehensive review of the phase dynamics in current-biased IJJs and argue the challenges of superconducting qubits utilizing IJJs.

In this paper, we propose a non-orthogonal multiple access with adaptive resource allocation. The proposed non-orthogonal multiple access assigns multiple frequency resources for each device to send packets. Even if the number of devices is more than that of the available frequency resources, the proposed non-orthogonal access allows all the devices to transmit their packets simultaneously for high capacity massive machine-type communications (mMTC). Furthermore, this paper proposes adaptive resource allocation algorithms based on factor graphs that adaptively allocate the frequency resources to the devices for improvement of the transmission performances. This paper proposes two allocation algorithms for the proposed non-orthogonal multiple access. This paper shows that the proposed non-orthogonal multiple access achieves superior transmission performance when the number of the devices is 50% greater than the amount of the resource, i.e., the overloading ratio of 1.5, even without the adaptive resource allocation. The adaptive resource allocation enables the proposed non-orthogonal access to attain a gain of about 5dB at the BER of 10-4.

This paper studies generalized variants of the MAXIMUM INDEPENDENT SET problem, called the MAXIMUM DISTANCE-d INDEPENDENT SET problem (MaxDdIS for short). For an integer d≥2, a distance-d independent set of an unweighted graph G=(V, E) is a subset S⊆V of vertices such that for any pair of vertices u, v∈S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r≥3) and planar graphs, as follows: (1) For every fixed integers d≥3 and r≥3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd-1)-approximation and O(rd-2/d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd-2/d)-approximation algorithms when restricted to d=r=3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

We studied whether a statement similar to the Ghouila-Houri's theorem might hold for alternating orientations of cocomparability graphs. In this paper, we give the negative answer. We prove that it is NP-complete to decide whether a cocomparability graph has an orientation that is alternating and acyclic. Hence, cocomparability graphs with an acyclic alternating orientation form a proper subclass of alternately orientable cocomparability graphs. We also provide a separating example, that is, an alternately orientable cocomparability graph such that no alternating orientation is acyclic.

We initiate the study of Ramsey numbers of trails. Let k≥2 be a positive integer. The Ramsey number of trails with k vertices is defined as the the smallest number n such that for every graph H with n vertices, H or the complete H contains a trail with k vertices. We prove that the Ramsey number of trails with k vertices is at most k and at least 2√k+Θ(1). This improves the trivial upper bound of ⌊3k/2⌋-1.

The adiabatic quantum flux parametron (AQFP) is an energy-efficient, high-speed superconducting logic device. To observe the tiny output currents from the AQFP in experiments, high-speed voltage drivers are indispensable. In the present study, we develop a compact voltage driver for AQFP logic based on a Josephson latching driver (JLD), which has been used as a high-speed driver for rapid single-flux-quantum (RSFQ) logic. In the JLD-based voltage driver, the signal currents of AQFP gates are converted into gap-voltage-level signals via an AQFP/RSFQ interface and a four-junction logic gate. Furthermore, this voltage driver includes only 15 Josephson junctions, which is much fewer than in the case for the previously designed driver based on dc superconducting quantum interference devices (60 junctions). In measurement, we successfully operate the JLD-based voltage driver up to 4 GHz. We also evaluate the bit error rate (BER) of the driver and find that the BER is 7.92×10-10 and 2.67×10-3 at 1GHz and 4GHz, respectively.

A Josephson parametric oscillator (JPO) is an interesting system from the viewpoint of quantum optics because it has two stable self-oscillating states and can deterministically generate quantum cat states. A theoretical proposal has been made to operate a network of multiple JPOs as a quantum annealer, which can solve adiabatically combinatorial optimization problems at high speed. Proof-of-concept experiments have been actively conducted for application to quantum computations. This article provides a review of the mechanism of JPOs and their application as a quantum annealer.

Some textbooks of formal languages and automata theory implicitly state the structural equality of the binary n-dimensional de Bruijn graph and the state diagram of minimum state deterministic finite automaton which accepts regular language (0+1)*1(0+1)n-1. By introducing special finite automata whose accepting states are refined with two or more colors, we extend this fact to both k-ary versions. That is, we prove that k-ary n-dimensional de Brujin graph and the state diagram for minimum state deterministic colored finite automaton which accepts the (k-1)-tuple of the regular languages (0+1+…+k-1)*1(0+1+…+k-1)n-1,...,and(0+1+…+k-1)*(k-1)(0+1+…+k-1)n-1 are isomorphic for arbitrary k more than or equal to 2. We also investigate the properties of colored finite automata themselves and give computational complexity results on three decision problems concerning color unmixedness of nondeterminisitic ones.

We review a new superconducting element, called “magnetic Josephson junctions” with a magnetic barrier instead of the insulating barrier of conventional Josephson junctions. We classify the three types of magnetic barrier, i.e., diluted alloy, conventional ferromagnet, and magnetic multilayer barriers, and introduce various new physics such as the π-state arising in magnetic Josephson junctions due to the interaction between superconductivity and magnetism.

We developed a Nb 4-layer process for fabricating superconducting integrated circuits that involves using caldera planarization to increase the flexibility and reliability of the fabrication process. We call this process the planarized high-speed standard process (PHSTP). Planarization enables us to flexibly adjust most of the Nb and SiO2 film thicknesses; we can select reduced film thicknesses to obtain larger mutual coupling depending on the application. It also reduces the risk of intra-layer shorts due to etching residues at the step-edge regions. We describe the detailed process flows of the planarization for the Josephson junction layer and the evaluation of devices fabricated with PHSTP. The results indicated no short defects or degradation in junction characteristics and good agreement between designed and measured inductances and resistances. We also developed single-flux-quantum (SFQ) and adiabatic quantum-flux-parametron (AQFP) logic cell libraries and tested circuits fabricated with PHSTP. We found that the designed circuits operated correctly. The SFQ shift-registers fabricated using PHSTP showed a high yield. Numerical simulation results indicate that the AQFP gates with increased mutual coupling by the planarized layer structure increase the maximum interconnect length between gates.

This review provides a current overview of the fabrication processes for superconducting digital circuits at CRAVITY (clean room for analog and digital superconductivity) at the National Institute of Advanced Industrial Science and Technology (AIST), Japan. CRAVITY routinely fabricates superconducting digital circuits using three types of fabrication processes and supplies several thousand chips to its collaborators each year. Researchers at CRAVITY have focused on improving the controllability and uniformity of device parameters and the reliability, which means reducing defects. These three aspects are important for the correct operation of large-scale digital circuits. The current technologies used at CRAVITY permit ±10% controllability over the critical current density (Jc) of Josephson junctions (JJs) with respect to the design values, while the critical current (Ic) uniformity is within 1σ=2% for JJs with areas exceeding 1.0 µm2 and the defect density is on the order of one defect for every 100,000 JJs.

Identifying the infection sources in a network, including the sponsor of a network rumor, the servers that inject computer virus into a computer network, or the zero-patient in an infectious disease network, plays a critical role in limiting the damage caused by the infection. A two-source estimator is firstly constructed on basis of partitions of infection regions in this paper. Meanwhile, the two-source estimation problem is transformed into calculating the expectation of permitted permutations count which can be simplified to a single-source estimation problem under determined infection region. A heuristic algorithm is also proposed to promote the estimator to general graphs in a Breadth-First-Search (BFS) fashion. Experimental results are provided to verify the performance of our method and illustrate variations of error detection in different networks.

This paper introduces the maximization version of the k-path vertex cover problem, called the MAXIMUM K-PATH VERTEX COVER problem (MaxPkVC for short): A path consisting of k vertices, i.e., a path of length k-1 is called a k-path. If a k-path Pk includes a vertex v in a vertex set S, then we say that v or S covers Pk. Given a graph G=(V, E) and an integer s, the goal of MaxPkVC is to find a vertex subset S⊆V of at most s vertices such that the number of k-paths covered by S is maximized. The problem MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs. We prove that MaxP3VC remains NP-hard even for split graphs. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time.

One goal in stack-queue mixed layouts of a graph subdivision is to obtain a layout with minimum number of subdivision vertices per edge when the number of stacks and queues are given. Dujmović and Wood showed that for every integer s, q>0, every graph G has an s-stack q-queue subdivision layout with 4⌈log(s+q)q sn(G)⌉ (resp. 2+4⌈log(s+q)q qn(G)⌉) division vertices per edge, where sn(G) (resp. qn(G)) is the stack number (resp. queue number) of G. This paper improves these results by showing that for every integer s, q>0, every graph G has an s-stack q-queue subdivision layout with at most 2⌈logs+q-1sn(G)⌉ (resp. at most 2⌈logs+q-1qn(G)⌉ +4) division vertices per edge. That is, this paper improves previous results more, for graphs with larger stack number sn(G) or queue number qn(G) than given integers s and q. Also, the larger the given integer s is, the more this paper improves previous results.

We study the problem of transforming one (vertex) c-coloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a c-coloring, where c denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant c ≥ 4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if c is a fixed constant. We then demonstrate that, even when c is a part of input, the problem is solvable in polynomial time for several graph classes, such as k-trees with any integer k ≥ 1, split graphs, and trivially perfect graphs.

The k-edge-connectivity augmentation problem for a specified set of vertices (kECA-SV for short) is defined by “Given a graph G=(V, E) and a subset Γ ⊆ V, find a minimum set E' of edges such that G'=(V, E ∪ E') has at least k edge-disjoint paths between any pair of vertices in Γ.” Let σ be the edge-connectivity of Γ (that is, G has at least σ edge-disjoint paths between any pair of vertices in Γ). We propose an algorithm for (σ+1)ECA-SV which is done in O(|Γ|) maximum flow operations. Then the time complexity is O(σ2|Γ||V|+|E|) if a given graph is sparse, or O(|Γ||V||BG|log(|V|2/|BG|)+|E|) if dense, where |BG| is the number of pairs of adjacent vertices in G. Also mentioned is an O(|V||E|+|V|2 log |V|) time algorithm for a special case where σ is equal to the edge-connectivity of G and an O(|V|+|E|) time one for σ ≤ 2.