Recommendation systems have been widely used in E-commerce sites, social media and etc. An important recommendation task is to predict items that a user will perform actions on with users' historical data, which is called top-K recommendation. Recently, there is huge amount of emerging items which are divided into a variety of categories and researchers have argued or suggested that top-K recommendation of item category could be very beneficial for users to make better and faster decisions. However, the traditional methods encounter some common but crucial problems in this scenario because additional information, such as time, is ignored. The ranking algorithm on graphs and the increasingly growing amount of online user behaviors shed some light on these problems. We propose a construction method of time-aware graphs to use ranking algorithm for personalized recommendation of item category. Experimental results on real-world datasets demonstrate the advantages of our proposed method over competitive baseline algorithms.

Ordered Binary Decision Diagrams (OBDDs for short) are popular dynamic data structures for Boolean functions. In some modern applications, we have to handle such huge graphs that the usual explicit representations by adjacency lists or adjacency matrices are infeasible. To deal with such huge graphs, OBDD-based graph representations and algorithms have been investigated. Although the size of OBDD representations may be large in general, it is known to be small for some special classes of graphs. In this paper, we show upper bounds and lower bounds of the size of OBDDs representing some intersection graphs such as bipartite permutation graphs, biconvex graphs, convex graphs, (2-directional) orthogonal ray graphs, and permutation graphs.

Computing an invariant of a graph such as treewidth and pathwidth is one of the fundamental problems in graph algorithms. In general, determining the pathwidth of a graph is NP-hard. In this paper, we propose several reduction methods for decreasing the instance size without changing the pathwidth, and implemented the methods together with an exact algorithm for computing pathwidth of graphs. Our experimental results show that the number of vertices in all chemical graphs in NCI database decreases by our reduction methods by 53.81% in average.

We are developing a fast Fourier transform (FFT) processor using high-speed and low-power single-flux-quantum (SFQ) circuits. Our main concern is the development of an SFQ butterfly processing circuit, which is the core processing circuit in the FFT processor. In our previous study, we have confirmed the complete operation of an integer-type butterfly processing circuit using the AIST 2.5 kA/cm$^{2}$ Nb standard process at the frequency of 25 GHz. In this study, we have designed an integer-type butterfly processing circuit using the AIST 10,kA/cm$^{2}$,Nb advanced process and confirmed its high-speed operation at the maximum frequency of 50,GHz.

The capacity (i.e., maximum flow) of a unicast network is known to be equal to the minimum s-t cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or unknown, it is not so trivial to predict statistical properties on the maximum flow of the network. In this paper, we present a probabilistic analysis for evaluating the accumulate distribution of the minimum s-t cut capacity on random graphs. The graph ensemble treated in this paper consists of undirected graphs with arbitrary specified degree distribution. The main contribution of our work is a lower bound for the accumulate distribution of the minimum s-t cut capacity. The feature of our approach is to utilize the correspondence between the cut space of an undirected graph and a binary LDGM (low-density generator-matrix) code. From some computer experiments, it is observed that the lower bound derived here reflects the actual statistical behavior of the minimum s-t cut capacity of random graphs with specified degrees.

An orthogonal ray graph is an intersection graph of horizontal and vertical rays (closed half-lines) in the plane. Such a graph is 3-directional if every vertical ray has the same direction, and 2-directional if every vertical ray has the same direction and every horizontal ray has the same direction. We derive some structural properties of orthogonal ray graphs, and based on these properties, we introduce polynomial-time algorithms that solve the dominating set problem, the induced matching problem, and the strong edge coloring problem for these graphs. We show that for 2-directional orthogonal ray graphs, the dominating set problem can be solved in O(n2 log5 n) time, the weighted dominating set problem can be solved in O(n4 log n) time, and the number of dominating sets of a fixed size can be computed in O(n6 log n) time, where n is the number of vertices in the graph. We also show that for 2-directional orthogonal ray graphs, the weighted induced matching problem and the strong edge coloring problem can be solved in O(n2+m log n) time, where m is the number of edges in the graph. Moreover, we show that for 3-directional orthogonal ray graphs, the induced matching problem can be solved in O(m2) time, the weighted induced matching problem can be solved in O(m4) time, and the strong edge coloring problem can be solved in O(m3) time. We finally show that the weighted induced matching problem can be solved in O(m6) time for orthogonal ray graphs.

A queue layout of a graph G consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. The queuenumber qn(G) is the minimum number of queues required in a queue layout of G. The Cartesian product of two graphs G1 = (V1,E1) and G2 = (V2,E2), denoted by G1 × G2, is the graph with {:v1 ∈ V1 and v2 ∈ V2} as its vertex set and an edge (,) belongs to G1×G2 if and only if either (u1,v1) ∈ E1 and u2 = v2 or (u2,v2) ∈ E2 and u1 = v1. Let Tk1,k2,...,kn denote the n-dimensional toroidal grid defined by the Cartesian product of n cycles with varied lengths, i.e., Tk1,k2,...,kn = Ck1 × Ck2 × … × Ckn, where Cki is a cycle of length ki ≥ 3. If k1 = k2 = … = kn = k, the graph is also called the k-ary n-cube and is denoted by Qnk. In this paper, we deal with queue layouts of toroidal grids and show the following bound: qn(Tk1,k2,...,kn) ≤ 2n-2 if n ≥ 2 and ki ≥ 3 for all i = 1,2,...,n. In particular, for n = 2 and k1,k2 ≥ 3, we acquire qn(Tk1,k2) = 2. Recently, Pai et al. (Inform. Process. Lett. 110 (2009) pp.50-56) showed that qn(Qnk) ≤ 2n-1 if n ≥1 and k ≥9. Thus, our result improves the bound of qn(Qnk) when n ≥2 and k ≥9.

A twin dominating set of a digraph D is a subset S of vertices if, for every vertex u ∉ S, there are vertices x,y ∈ S such that ux and yu are arcs of D. A digraph D is round if the vertices can be labeled as v0,v1,...,vn-1 so that, for each vertex vi, the out-neighbors of vi appear consecutively following vi and the in-neighbors of vi appear consecutively preceding vi. In this paper, we give polynomial time algorithms for finding a minimum weight twin dominating set and a minimum weight total twin dominating set for a weighted round digraph. Then we show that there is a polynomial time algorithm for deciding whether a locally semicomplete digraph has an independent twin dominating set. The class of locally semicomplete digraphs contains round digraphs as a special case.

Consider a simple undirected graph G = (V,E) with vertex set V and edge set E. Let G-u be a subgraph induced by the vertex set V-{u}. The distance δG(x,y) is defined as the length of the shortest path between vertices x and y in G. The vertex u ∈ V is a hinge vertex if there exist two vertices x,y ∈ V-{u} such that δG-u(x,y)>δG(x,y). Let U be a set consisting of all hinge vertices of G. The neighborhood of u is the set of all vertices adjacent to u and is denoted by N(u). We define d(u) = max{δG-u(x,y) | δG-u(x,y)>δG(x,y),x,y ∈ N(u)} for u ∈ U as detour degree of u. A maximum detour hinge vertex problem is to find a hinge vertex u with maximum d(u) in G. In this paper, we proposed an algorithm to find the maximum detour hinge vertex on an interval graph that runs in O(n2) time, where n is the number of vertices in the graph.

We have been developing a superconducting time-of-flight mass spectrometry (TOF-MS) system, which utilizes a superconductive strip ion detector (SSID) and a single-flux-quantum (SFQ) multi-stop time-to-digital converter (TDC). The SFQ multi-stop TDC can measure the time intervals between multiple input signals and directly convert them into binary data. In this study, we designed and implemented 24-bit SFQ multi-stop TDCs with a 3×24-bit FIFO buffer using the AIST Nb standard process (STP2), whose time resolution and dynamic range are 100ps and 1.6ms, respectively. The timing jitter of the TDC was investigated by comparing two types of TDCs: one uses an on-chip SFQ clock generator (CG) and the other uses a microwave oscillator at room temperature. We confirmed the correct operation of both TDCs and evaluated their timing jitter. The experimentally-obtained timing jitter is about 40ns and 700ps for the TDCs with and without the on-chip SFQ CG, respectively, for the measured time interval of 50µs, which linearly increases with increase of the measured time interval.

We present our design and operation of a 6-bit quasi-triangle voltage waveform generator comprising three circuit blocks; an improved variable Pulse Number Multiplier (variable-PNM), a Code Generator (CG), and a Double-Flux-Quantum Amplifier (DFQA). They are integrated into a single chip using a niobium Josephson junction technology. While the multiplication factor of our previous m-bit variable-PNM was limited between 2m-1 and 2m, that of the improved one is extended between 1 and 2m. Correct operations of the 6-bit variable-PNM are confirmed in low-speed testing with respect to the codes from the CG, whereas generation of a 6-bit, 0.20mVpp quasi-triangle voltage waveform is demonstrated with the 10-fold DFQA in high-speed testing.

We describe the recent progress on a Nb nine-layer fabrication process for large-scale single flux quantum (SFQ) circuits. A device fabricated in this process is composed of an active layer including Josephson junctions (JJ) at the top, passive transmission line (PTL) layers in the middle, and a DC power layer at the bottom. We describe the process conditions and the fabrication equipment. We use both diagnostic chips and shift register (SR) chips to improve the fabrication process. The diagnostic chip was designed to evaluate the characteristics of basic elements such as junctions, contacts, resisters, and wiring, in addition to their defect evaluations. The SR chip was designed to evaluate defects depending on the size of the SFQ circuits. The results of a long-term evaluation of the diagnostic and SR chips showed that there was fairly good correlation between the defects of the diagnostic chips and yields of the SRs. We could obtain a yield of 100% for SRs including 70,000JJs. These results show that considerable progress has been made in reducing the number of defects and improving reliability.

Given a simple connected graph G with n vertices, the spanning tree problem involves finding a tree that connects all the vertices of G. Solutions to this problem have applications in electrical power provision, computer network design, circuit analysis, among others. It is known that highly efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper superclasses of trapezoid graphs. In this paper, we propose an O(n) time algorithm for the spanning tree problem on a circular trapezoid graph. Moreover, this algorithm can be implemented in O(log n) time with O(n/log n) processors on EREW PRAM computation model.

The gathering problem of anonymous and oblivious mobile robots is one of the fundamental problems in the theoretical mobile robotics. We consider the gathering problem in unoriented and anonymous rings, which requires that all robots eventually keep their positions at a common non-predefined node. Since the gathering problem cannot be solved without any additional capability to robots, all the previous results assume some capability of robots, such as the agreement of local view. In this paper, we focus on the multiplicity detection capability. This paper presents a deterministic gathering algorithm with local-weak multiplicity detection, which provides a robot with information about whether its current node has more than one robot or not. This assumption is strictly weaker than that in previous works. Our algorithm achieves the gathering from an aperiodic and asymmetric configuration with 2 < k < n/2 robots, where n is the number of nodes. We also show that our algorithm is asymptotically time-optimal one, i.e., the time complexity of our algorithm is O(n). Interestingly, despite the weaker assumption, it achieves significant improvement compared to the previous algorithm, which takes O(kn) time for k robots.

Given a graph G = (V,E) together with a nonnegative integer requirement on vertices r:V Z+, the annotated edge dominating set problem is to find a minimum set M ⊆ E such that, each edge in E - M is adjacent to some edge in M, and M contains at least r(v) edges incident on each vertex v ∈ V. The annotated edge dominating set problem is a natural extension of the classical edge dominating set problem, in which the requirement on vertices is zero. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the annotated edge dominating set problem in graphs with maximum degree 3 can be solved in O*(1.2721n) time and polynomial space, where n is the number of vertices in the graph. We also show that there is an O*(2.2306k)-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an annotated edge dominating set of size k or not.

Let Gs=(Vs, Es) be a simple connected graph. A vertex v ∈ Vs is an articulation vertex if deletion of v and its incident edges from Gs disconnects the graph into at least two connected components. Finding all articulation vertices of a given graph is called the articulation vertex problem. A vertex u ∈ Vs is called a hinge vertex if there exist any two vertices x and y in Gs whose distance increase when u is removed. Finding all hinge vertices of a given graph is called the hinge vertex problem. These problems can be applied to improve the stability and robustness of communication network systems. In this paper, we propose linear time algorithms for the articulation vertex problem and the hinge vertex problem of circular permutation graphs.

PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n8) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs and an O(n4(n+m)) time algorithm for PREIMAGE CONSTRUCTION on distance-hereditary graphs, where n is the number of graphs in the input, and m is the number of edges in a preimage. Since each graph of the input has n-1 vertices and O(n2) edges, the input size is O(n3) (, or O(nm)). There are polynomial time isomorphism algorithms for permutation graphs and distance-hereditary graphs. However the number of permutation (distance-hereditary) graphs obtained by adding a vertex to a permutation (distance-hereditary) graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point.

We outline a number of high temperature superconducting Josephson junction-based devices including superconducting quantum interference devices (SQUIDs) developed for a wide range of applications including geophysical exploration, magnetic anomaly detection, terahertz (THz) imaging and microwave communications. All these devices are based on our patented technology for fabricating YBCO step-edge junction on MgO substrates. A key feature to the successful application of devices based on this technology is good stability, long term reliability, low noise and inherent flexibility of locating junctions anywhere on a substrate.

In this letter, distributed source coding with one distortion criterion and correlated messages is considered. This problem can be regarded as “Berger-Yeung problem with correlated messages”. It corresponds to the source coding part of the graph-based framework for transmission of a pair of correlated sources over the multiple-access channel where one is lossless and the other is lossy. As a result, the achievable rate-distortion region for this problem is provided. A rigorous proof of both achievability and converse part is also given.

Superconducting integrated circuits should be operated at low temperature below a half of their critical temperatures. Thermal heat from a bias resistor could rise the temperature in Josephson junctions, and would reduce their critical currents. In this study, we estimate the temperature in a Josephson junction heated by a bias resistor at the bath temperature of 4.2 K, and introduce a parameter β that connects the thermal heat from a bias resistor and the temperature elevation of a Josephson junction. By using β, the temperature in the Josephson junction can be estimated as functions of the current through the resistor.