Masakuni TAKI Mikihito SUGIURA Toshinobu KASHIWABARA
A kind of online edge-coloring problems on bipartite graphs is considered. The input is a graph (typically with no edges) and a sequence of operations (edge addition and edge deletion) under the restriction that at any time the graph is bipartite and degree-bounded by k, where k is a prescribed integer. At the time of edge addition, the added edge can be irrevocably assigned a color or be left uncolored. No other coloring or color alteration is allowed. The problem is to assign colors as many times as possible using k colors. Two algorithms are presented: one with competitiveness coefficient 1/4 against oblivious adversaries, and one with competitiveness coefficient between 1/4 and 1/2 with the cost of requiring more random bits than the former algorithm, also against oblivious adversaries.
We present a simple solution to secretly sharing a factoring witness (for given N) in a publicly-verifiable manner. Compared to the previous PVSS schemes to secretly sharing a factoring witness, the scheme enjoys the following properties: (1) the formal proofs of security can be given; (2) it is designed to be conceptually simpler; (3) it needs fewer communicated bits and, if not-so low exponent RSA (e.g., e > 219+1) is used in the previous schemes, fewer computations; (4) no general multi-party computation is required in the preparation phase.
Jung-Sik JEONG Kei SAKAGUCHI Jun-ichi TAKADA Kiyomichi ARAKI
It is known that MUSIC and ESPRIT algorithms can estimate simultaneously both the instantaneous Direction of Arrival (DOA) and the instantaneous Angular Spread (AS) in multiple scattering environments. These algorithms use the Extended Array Mode Vector (EAMV) with complex angle. The previous work evaluated the performance of those algorithms by comparing the estimated DOA and the estimated AS with the DOA and the AS given in the EAMV, which uses the first-order approximation. Thus, this evaluation method has not clearly reflected the estimation accuracy of MUSIC and ESPRIT. This paper presents the joint estimation performance of MUSIC and ESPRIT by introducing the criteria for evaluation. For this, the spatial signature (SS) is reconstructed from the estimates of the DOA and the AS, and compared to the true SS in the meaning of data fitting.
Koji CHIDA Shigenori UCHIYAMA Taiichi SAITO
Since the invention of the RSA scheme, a lot of public-key encryption and signature schemes based on the intractability of integer factoring have been proposed. Most employ integers of the form N = p q, such as the RSA scheme, but some employ integers of the form N = pr q. It has been reported that RSA decryption speed can be greatly improved by using N = pr q integers for large r. On the other hand, Boneh et al. proposed a novel integer factoring method for integers such as N = pr q for large r. This factoring algorithm, the so-called Lattice Factoring Method, is based on the LLL-algorithm. This paper proposes a new method for factoring integers of the form N = pr q for large r and gives a new characterization of r such that factoring integers N = pr q is easier. More precisely, the proposed method strongly depends on the size and smoothness of the exponent, r. The theoretical consideration of and implementation of our method presented in this paper show that if r satisfies a certain condition our method is faster than both Elliptic Curve Method and Lattice Factoring Method. In particular, the theoretical consideration in this paper mainly employs the techniques described in the excellent paper by Adleman, Pomerance and Rumely that addresses primality testing.
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.
This letter is concerned with a performance analysis of a VPG DS/CDMA acquisition system employing a reference filter based on the statistical evaluation of the decision threshold. The probabilities of detection and false alarm are derived, and the mean acquisition time is evaluated as a measure of the system performance. From the results, it is shown that in the performance analysis of the parallel acquisition system with reference filtering, the statistical evaluation of the decision threshold seems more appropriate than the approximation of the decision threshold adopted in other acquisition schemes.
Nowadays, the World Wide Web is continuing to expand at an amazing rate as a medium for conducting business in addition to disseminating information, and Web users are remarkably increasing. Human activities in virtual space as the Web are producing large volumes of data, and Web data mining to extract information from Web data has become an important research area. In this paper, we examine the features of Web log data and propose a method for transaction identification. We also introduce a new problem of user segmentation and present a method for solving this problem.
Toshihiro IWAMOTO Yasuhiko JIMBO Kazuyuki AIHARA
We propose a novel method for analysis of time-related neuronal activities. This method can be used for the detection of firing patterns in the presence of noise, which is inevitable in physiological experiments. This method is also useful for probability density estimation, because it enables precise information quantification from a small amount of data.
Atsuo HAZEYAMA Naota SAWABE Seiichi KOMIYA
The group organization used for group learning in a knowledge intensive domain like software development affects educational achievement. This paper proposes a group organization system for software engineering education done through group learning. The organizational problem itself is defined and why a Genetic Algorithm (GA) is an appropriate means of solving this problem is explained. This system is a Web application developed with open source software and runs on an open source software platform. Based on the group organization data collected from actual classes, we generated various group organizations by using different strategy parameter values. We then gave a questionnaire to actual students asking them which solution produced the fairest group organization. The replies received revealed that the candidate solution that set greater weight on leadership capability and system analysis capability was the fairest.
Masao TSUKITANI Eiji YANADA Takatoshi KATO Eisuke SASAOKA Yoshinori MAKIO
This paper describes design optimization and performances of hybrid optical transmission lines consisting of effective-area-enlarged pure silica core fiber and dispersion compensating fiber. As a result of the design optimization, considering low nonlinearity and good bending characteristic, the developed fibers exhibit a span average loss of 0.208 dB/km, a span average dispersion slope of 0.02 ps/nm2/km and low nonlinearity with an equivalent effective area of 60 µm2. Further optimization of the relationship among the nonlinearity, the dispersion slope and the bending characteristic enables perfectly dispersion-flattened hybrid optical transmission lines exhibiting a low transmission loss of 0.211 dB/km, low nonlinearity with an equivalent effective area of 60 µm2 and small dispersion deviation of 0.03 ps/nm/km in a wavelength band wider than 40 nm.
Shadan SANIEPOUR E. Behrouz Homayoun FAR
Network traffic characteristics impacts directly network performance, and resource allocation policies. In this work, we introduce a multi-agent system, that manages the performance of web servers with minimal cost of mirroring. In our proposed system each web server is viewed as a software agent that perceives its environment by monitoring its traffic. The goal of the agent is to manage the performance, using cooperative mirror servers, while minimizing the cost of mirroring. Communication between the agents enables each web server to decide about its future actions, which is whether to share its load with the cooperative mirror servers, and how much load to assign to them. The architecture of a software agent that is intended to manage the performance of a web server, is elaborated and its different modules are described. Also a set of cooperative agents is defined, that form a multi-agent system and is intended to assure maintaining the performance with minimal cost of mirroring. The experimental results presented in this article illustrates the effectiveness of the proposed system.
A communication model and a computer assisted communication method are introduced. With this model incorrect communications between humans are explained and then a method to lead successful communications with computer is illustrated. This method improves qualities of communications and can be applied to co-operative works. On the basis of the communication method, we have been developing a co-operative visual software requirements definition method via network with a visual requirements language named VRDL. Our method will improve quality of software requirements specification (SRS).
Hiroshige OHNO Hiroshi NARUSE Toshio KURASHIMA Atsushi NOBIKI Yasuomi UCHIYAMA Yuki KUSAKABE
We applied a Brillouin-OTDR, which is a distributed optical fiber strain sensor, to two actual concrete piles. The piles were made for use as highway foundations by on-site-pouring at construction sites and underwent load testing to ensure that their characteristics satisfied the required levels. Compressive strain caused by the load exerted on the piles was measured to an accuracy of 0.01% and a spatial resolution of 1 m. This measurement was obtained by embedding a strain-sensing optical fiber in the piles during construction. The results showed that there was good agreement between the measured strain and both the theoretical values and the values obtained with a conventional strain gauge based on electric resistance. Furthermore, the obtained strain distribution reflected the effects of friction between the pile surface and the ground. These results demonstrate the effectiveness of the Brillouin-OTDR for this kind of testing and also as a means of obtaining detailed data on the strain in concrete piles.
Ock-Kyung YOON Dong-Min KWAK Bum-Soo KIM Dong-Whee KIM Kil-Houm PARK
This paper proposed an automated segmentation algorithm for MR brain images through the complementary use of T1-weighted, T2-weighted, and PD images. The proposed segmentation algorithm is composed of 3 steps. The first step involves the extraction of cerebrum images by placing a cerebrum mask over the three input images. In the second step, outstanding clusters that represent the inner tissues of the cerebrum are chosen from among the 3-dimensional (3D) clusters. The 3D clusters are determined by intersecting densely distributed parts of a 2D histogram in 3D space formed using three optimal scale images. The optimal scale image results from applying scale-space filtering to each 2D histogram and a searching graph structure. As a result, the optimal scale image can accurately describe the shape of the densely distributed pixel parts in the 2D histogram. In the final step, the cerebrum images are segmented by the FCM (Fuzzy c-means) algorithm using the outstanding cluster center value as the initial center value. The ability of the proposed segmentation algorithm to calculate the cluster center value accurately then compensates for the current limitation of the FCM algorithm, which is unduly restricted by the initial center value used. In addition, the proposed algorithm, which includes a multi spectral analysis, can achieve better segmentation results than a single spectral analysis.
Yuu ISHII Kensuke SHIMA Satoshi OKUDE Kenji NISHIDE Akira WADA
We investigate a method to suppress the polarization-dependent loss (PDL) of long-period fiber gratings (LPFGs). We study the origins of the PDL and propose an azimuthally isotropic UV exposure to suppress the UV-induced birefringence and to realize low-PDL LPFGs. By using this technique and a low birefringent fiber together, the PDL of LPFGs can be reduced to a sufficiently low level required in high performance communication systems. Moreover, the validity of our theoretical modeling is confirmed by the experimental results.
Mitsuru KIHARA Katsumi HIRAMATSU Masaki SHIMA Shigeru IKEDA
We have developed a distributed optical fiber strain sensor for detecting the collapse of river embankments. The sensor uses a Brillouin optical time domain reflectometer (BOTDR) and consists of an optical fiber cable and pieces of nonwoven cloth. Pieces of cloth are fixed to the cable at 1.5-meter intervals and it is then embedded in a U-shaped configuration in a river embankment. The pieces of cloth are displaced when there is movement of the soil in which they are embedded. If one of two adjacent pieces of cloth remains stationary while the other moves, the optical fiber between the two pieces is stretched. The collapse of an embankment can be detected by using a BOTDR to monitor any such stretching in the 1.5-m lengths of fiber. The developed sensor operates at a sensitivity of 0.025%/kgf, which is equivalent to 0.067%/mm, and is thus capable of detecting soil movements of a few mm in river embankments. The sensor is also able to provide effective advance warning of the collapse of a river embankment resulting from water penetration. We subjected the sensor system to field tests that demonstrated the effectiveness of its construction and its long-term stability. The developed sensor system is an effective tool for use in river management systems of the very near future.
Yasuo KOKUBUN Takashi KATO Sai Tak CHU
The Lorentzian-shape filter response of a microring resonator filter is not suitable to the practical use in WDM systems, because of the lack of pass band flatness, high cross talk, and the large wing in the stop band. Therefore, the tailoring of filter response shape is required to improve the performance. In this paper, the authors designed and demonstrated the box-like filter response of microring resonator filter by using the supermodes of stacked double microring resonators. The thicknesses of microrings and the separation between them were optimally designed to give the maximally flat response. A fine fabrication process was developed to achieve the deep and very smooth side wall. The shape factor, which is defined by the ratio of -1 dB bandwidth to -10 dB bandwidth, was successfully improved by three factors from 0.17 of Lorentzian shape to 0.51.
Hironori WAKANA Masaki FUJIBAYASHI Noriyoshi FUSHIMI Osamu MICHIKAMI
By depositing insulating layers on oxide superconducting films, the films generally deteriorate. When an insulating multilayer of CeO2(50 )
Nazia Jabeen ALI Akinobu IRIE Gin-ichiro OYA
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.
Lan ZHANG Masataka MORIYA Takayuki KOBAYASHI Masashi MUKAIDA Toshinari GOTO
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.