In this paper, we propose a method for detecting conserved domains from a set of amino acid sequences that belong to a protein family. This method detects the domains as follows: first, generate fixed-length subsequences from the sequences; second, construct a weighted graph that connects any two of the subsequences (vertices) having higher similarity than a pre-defined threshold; third, search for the maximum-density subgraph for each connected component of the graph; finally, explore conserved domains in the sequences by combining the results of the previous step. From the performance results obtained by applying the method to several protein families that have complex conserved domains, we found that our method was able to detect those domains even though some domains were weakly conserved.

Dislocation properties in InGaN/GaN Quantum Wells and GaN grown on bulk GaN and sapphire substrates by metalorganic chemical vapor deposition (MOCVD) were characterized using cathodoluminescnece (CL), transmission electron microscopy (TEM), atomic force microscopy (AFM) and photoluminescence (PL). It was clearly demonstrated that dislocations act as nonradiative recombination centers in both n-type (undoped and Si-doped) GaN and InGaN layers. Furthermore the very short-minority carrier diffusion length was a key parameter to explain the high light emission efficiency in GaN-based light emitting diodes (LEDs) prepared on sapphire substrates. On the other side band-tail states were detected in the heteroepitaxial InGaN layers only by temperature dependence PL measurement. Additionally InGaN phase separation, which consists of few micron domains, has been produced under growth conditions which favors the spiral growth. These results indicate that the dislocations in the InGaN layers act as triggering centers for the InGaN phase separation which cause both a compositional fluctuation and the formation of few micron phase separated domains. The homoepitaxial InGaN layers showed however quite normal behaviors for all characterizations.

Bit error rates (BER) for playback of (1,7) code employed in optical disc recording were simulated using an ideal (Gaussian) playback waveform, with playback being performed by PRML (Partial Response Maximum-Likelihood) combining a partial response equalizer and a double clock weighted Viterbi decoder. It was found that best BER occurs for PR(2,3,3,2) +7/10 level Viterbi decoding at a weighted value of w = 0.5 for data consisting of 107 symbols. For a minimum bit length of 0.28 µm, BER of 10-4 and less than 10-6 was obtained for SN ratios of 15.6 dB and 17.7 dB, respectively. And for a minimum bit length of 0.26 µm, BER of 10-4 and less than 10-6 was obtained for SN ratios of 16.7 dB and 18.8 dB, respectively. These results demonstrate the feasibility of a minimum bit length of 0.26 µm in current optical disc recorders.

This paper presents a non-interactive and optimally resilient distributed multiplication scheme. By non-interactive we mean that the players need to use outgoing communication channels only once without the need to synchronize with the other players as long as no disruption occurs. Our protocol withstands corrupt players up to less than the half of the players, so it provides optimal resiliency. Furthermore, the shared secrets are secure even against infinitely powerful adversaries. The security is proven under the intractability assumption of the discrete logarithm problem. Those properties are achieved by using an information theoretically secure non-interactive verifiable secret sharing as a kind of non-interactive proof system between a single prover and distributed verifiers. Compared to a former interactive solution in the same setting, the cost is an increase in local computation and communication complexity that is determined by the factor of the threshold used in the verifiable secret sharing.

Let S be a set of n points in the plane and CH(S) be the convex hull of S. We consider the problem of constructing an approximate convex hull which contains CH(S) with strong convexity. An ε-convex δ-superhull of S is a convex polygon P satisfying the following conditions: (1) P has at most O(n) vertices, (2) P contains S, (3) no vertex of P lies farther than δ outside CH(S), and (4) P remains convex even if its vertices are perturbed by as much as ε. The parameters ε and δ represent the strength of convexity of P and the degree of approximation of P to CH(S), respectively. This paper presents the first parallel method for the problem. We show that an ε-convex (8+42)ε-superhull of S can be constructed in O(log n) time using O(n) processors, or in O(log n) time using O(n/log n) processors if S is sorted, in the EREW-PRAM model. We implement the algorithm and find that the average performance is even much better: the results are more strongly convex and much more approximate to CH(S) than the theoretical analysis shows.

Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.

The sense of equilibrium is influenced by various factors of visual stimulation, especially far peripheral vision and a motion parallax. An investigation of these two factors was made in order to apply the findings to construct a rehabilitation method for equilibrium disorders. From the experimental results, it was found that the center of gravity for the subjects was greatly affected by both far peripheral vision and the motion parallax. This finding suggests how visual stimulation should be displayed to control the sense of balance in the case of equilibrium disorders.

This paper proposes an intelligent image interpolation method based on Cubic Hermite procedure for improving digital images. Image interpolation has been used to create high-resolution effects in digitized image data, providing sharpness in high frequency image data and smoothness in low frequency image data. Most interpolation techniques proposed in the past are centered on determining pixel values using the relationship between neighboring points. As one of the more prevalent interpolation techniques, Cubic Hermite procedure attains the interpolation with a 3rd order polynomial fit using derivatives of points and adaptive smoothness parameters. Cubic Hermite features many forms of a curved shape, which effectively reduce the problems inherent in interpolations. This paper focuses on a method that intelligently determines the derivatives and adaptive smoothness parameters to effectively contain the interpolation error, achieving significantly improved images. Derivatives are determined by taking a weighted sum of the neighboring points whose weighting function decreases as the intensity difference of neighboring points increases. Smoothness parameter is obtained by training an exemplar image to fit into the Cubic Hermite function such that the interpolation error is minimized at each interpolating point. The simulations indicate that the proposed method achieves improved image results over that of conventional methods in terms of error and image quality performance.

This paper proposes a Space-Time Object Model, an object oriented model that possesses space and time management mechanisms. The goal of this object model is to provide a common software infrastructure for implementing large-scale moving object simulations efficiently, such as car traffic simulations and disaster evacuation simulations, using a direct mapping scheme on a parallel and distributed computing environment. In this object model, the software infrastructure provides two principal functions, "Space Management" and "Time Management," which allows programmers to focus on application programming instead of parallel programming. Although there are several known infrastructure software, which provide the environment needed to develop and execute parallel and distributed simulations, they only provide a "Time Management" mechanism. In this paper, we present a Space-Time Object Model and an overview of a program called OSim, which is an implementation of the Space-Time Object Model. Then, we demonstrate the applicability and efficiency of this model by introducing the overview and evaluation results of a parallel car traffic simulation system using OSim.

Given a combinatorial problem on a set of weighted elements, if we change the weight using a parameter, we obtain a parametric version of the problem, which is often used as a tool for solving mathematical programming problems. One interesting question is how to describe and analyze the trajectory of the solution. If we consider the trajectory of each weight function as a curve in a plane, we have a set of curves from the problem instance. The curves induces a cell complex called an arrangement, which is a popular research target in computational geometry. Especially, for the parametric version of the problem of computing the minimum weight base of a matroid or polymatroid, the trajectory of the solution becomes a subcomplex in an arrangement. We introduce the interaction between the two research areas, combinatorial optimization and computational geometry, through this bridge.

This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k 3 as far as k is a fixed constant. For the case k=2, effective use of geometric property of an optimal solution leads to considerable improvement on the computational complexity. Other related topics are also discussed.

This paper analyzes what structural features of graph problems allow efficient parallel algorithms. We survey some parallel algorithms for typical problems on three kinds of graphs, outerplanar graphs, trapezoid graphs and in-tournament graphs. Our results on the shortest path problem, the longest path problem and the maximum flow problem on outerplanar graphs, the minimum-weight connected dominating set problem and the coloring problem on trapezoid graphs and Hamiltonian path and Hamiltonian cycle problem on in-tournament graphs are adopted as working examples.

Consider a set of parties who do not trust each other but want to compute some agreed function of their inputs in a secure way. This problem is known as multi-party computation. It has various interesting applications including election over the internet, electric contracts, private and secret database, joint signatures, and others. A number of techniques for the problem have been proposed. Secure protocols for multi-paty computation known so far are mainly based on threshold secret sharing, verifiable secret sharing, zero-knowledge proofs, and error-correcting codes. We survey important and interesting results on secure multi-party computation under the existence of various types of adversaries.

The two dimensional mesh is widely considered to be a promising parallel architecture in its scalability. In this architecture, processors are naturally placed at intersections of horizontal and vertical grids, while there can be three different types of communication links: (i) The first type is the most popular model, called a mesh-connected computer: Each processor is connected to its four neighbours by local connections. (ii) Each processor of the second type is connected to a couple of (row and column) buses. The system is then called a mesh of buses. (iii) The third model is equipped with both buses and local connections, which is called a mesh-connected computer with buses. Mesh routing has received considerable attention for the last two decades, and a variety of algorithms have been proposed. This paper provides an overview of lower and upper bounds for algorithms, with pointers to the literature, and suggests further research directions for mesh routing.

An epoxy-modified urethane rubber mixed with carbon particles is now chosen as the millimeter-wave absorber material in our study. The absorption characteristics of the absorber is measured under temperature changes. The weatherability of our absorber is also clarified based on absorption characteristics, thickness and hardness of the sample. As a result of the temperature characteristics of the absorber, the difference of the maximum absorption frequency under temperature changes is about 1 GHz, however the absorption of 20 dB or more is obtained between 54 and 58 GHz. The result of accelerated artificial exposure test is that 2.8% of the thickness of our sample is shrunk after 1000 hour exposure, and the hardness of rubber is hardened with increasing test time. It is also confirmed that the deterioration of the absorption ranges from 1 to 3 dB, although the absorption of about 20 dB is kept at the frequency range. As a consequence, it is confirmed that the wave absorber using the epoxy-modified urethane rubber mixed with carbon particles has good weatherability including our desired temperature characteristics, and it is suitable for outdoor use.

In a phase-locked-loop (PLL) frequency synthesizer with binary phase comparison, jitter is hard to suppress. In this paper, we propose a PLL frequency synthesizer with an improved binary phase comparison which can solve the above problem. The effectiveness of the proposed method is confirmed by PSpice simulation results.

A convex hull is one of the most fundamental and interesting geometric constructs in computational geometry. Considerable research effort has focused on developing algorithms, both in serial and in parallel, for computing convex hulls. In particular, there are few problems whose parallel algorithms are so thoroughly studied as convex hull problems. In this paper, we review the convex hull parallel algorithms and their paradigm. We provide a summary of results and introduce several interesting topics including typical techniques, output-size sensitive methods, randomized approaches, and robust algorithms for convex hull problems, with which we may see the highlights of the whole research for parallel algorithms. Most of our discussion uses the PRAM (Parallel Random Access Machine) computational model, but still we give a glance at the results of the other parallel computational models such as mesh, mesh-of-trees, hypercube, recofigurable array, and models of coarse grained multicomputers like BSP and LogP.

A reliable and automatic parameter extraction technique for DFB lasers is developed. The parameter extraction program which is named "LAPAREX" is able to determine many device parameters from a measured sub-threshold spectrum only, including gain- and index-coupling coefficients, and spatial phases of the grating at front and rear facets. Injection current dependence of coupling coefficients in a gain-coupled DFBlaser is observed, for the first time, by making use of it.

It is important to establish the technology to accommodate best effort TCP/IP traffic over wide area ATM networks. The UBR (Unspecified Bit Rate) service category is the most typical service category for the best effort traffic, especially in the LAN environment. On the other hand, the VBR (Variable Bit Rate) service category with SCD (Selective Cell Discard) option is considered as the service category which is appropriate for wide area networks due to its fairness and minimum guarantee of the cell transmission using not only PCR (Peak Cell Rate) but SCR (Sustainable Cell Rate) and MBS (Maximum Burst Size). However, there is no actual evaluation for such service. We have, therefore, performed the experimental studies on TCP/IP over VBR with SCD along with UBR and VBR without SCD by VC (Virtual Channel) level policing when each TCP connection is mapped to a different VC. Through these experiments, we measured the link utilization of the effective data and the fairness between each obtained TCP throughput during the congestion of the ATM switch. From the results of the link utilization, the value is over 95% under the various conditions. Therefore, even in the case of the cell losses due to SCD or buffer overflow in ATM switch congestion, average throughput is almost the same as the value which equals the trunk line speed divided by the number of the accommodated TCP connections. From the results of the fairness, VBR with SCD per VC is better than UBR and also obtains better TCP throughput than VBR without SCD. Furthermore, to confirm those characteristics more generally, we adopt the accommodated TCP connections not only with the same TCP send/receive socket buffer size but with different sizes. Finally, we discuss the effectiveness between VBR with SCD and the other service categories, such as UBR and ABR (Available Bit Rate) and GFR (Guaranteed Frame Rate), and conclude that VBR with SCD is one of the most suitable ATM service categories for accommodating best effort traffic.

To provide QoS guarantees for each connection, efficient scheduling algorithms, such as WFQ, have been proposed. These algorithms assume a certain amount of buffer is allocated for each connection to provide loss free transmission of packets. This buffer allocation policy, however, requires much buffer space especially when many connections are sharing a link. In this paper we propose the use of partial buffer sharing (PBS) policy combined with usage parameter control (UPC) for efficient buffer management and flexible QoS control in ATM switches. We evaluate the feasibility of the proposed method by solving a Markov model. We also show that using the proposed method, we can control the cell loss ratio (CLR) independently of the delay. Numerical evaluations are presented, which indicates the PBS combined with UPC significantly reduces the buffer size required to satisfy given cell loss ratios.