Finding the longest common nonsuperstring in linear time

String inclusion and non-inclusion problems have been vigorously studied in such diverse fields as molecular biology, data compression, and computer security. Among the well-known string inclusion or non-inclusion notions, we are interested in the longest common nonsuperstring. Given a set of strings, the longest common nonsuperstring problem is finding the longest string that is not a superstring of any string in the given set. It is known that the longest common nonsuperstring problem is solvable in polynomial time.In this paper, we propose an efficient algorithm for the longest common nonsuperstring problem. The running time of our algorithm is linear with respect to the sum of the lengths of the strings in the given set, using generalized suffix trees.     

Improving multikey Quicksort for sorting strings with many equal elements

Bentley and Sedgewick proposed multikey Quicksort with ‘split-end’ partitioning for sorting strings. But it can be slow in case of many equal elements because it adopted ‘split-end’ partitioning that moves equal elements to the ends and swaps back to the middle. We present ‘collect-center’ partitioning to improve multikey Quicksort in that case. It moves equal elements to the middle directly like the ‘Dutch National Flag Problem’ partitioning approach and it uses two inner loops like Bentley and McIlroy's. In case of many equal elements such as DNA sequences, HTML files, and English texts, multikey Quicksort with ‘collect-center’ partitioning is faster than multikey Quicksort with ‘split-end’ partitioning.     

Local and singularity-free G 1 triangular spline surfaces using a minimum degree scheme

We develop a scheme for constructing G ¹ triangular spline surfaces of arbitrary topological type. To assure that the scheme is local and singularity-free, we analyze the selection of scalar weight functions and the construction of the boundary curve network in detail. With the further requirements of interpolating positions, normals, and surface curvatures, we show that the minimum degree of such a triangular spline surface is 6. And we present a method for constructing boundary curves network, which consists of cubic Bézier curves. To deal with certain singular cases, the base mesh must be locally subdivided and we proposed an adaptive subdivision strategy for it. An application of our G ¹ triangular spline surfaces to the approximation of implicit surfaces is described. The visual quality of this scheme is demonstrated by some examples.     

Fully discrete potential-based finite element methods for a transient eddy current problem

Fully discrete potential-based finite element methods called methods are used to solve a transient eddy current problem in a three-dimensional convex bounded polyhedron. Using methods, fully discrete coupled and decoupled numerical schemes are developed. The existence and uniqueness of solutions for these schemes together with the energy-norm error estimates are provided. To verify the validity of both schemes, some computer simulations are performed for the model from TEAM Workshop Problem 7. This work was supported by Postech BSRI Research Fund-2009, National Basic Research Program of China (2008CB425701), NSFC under the grant 10671025 and the Key Project of Chinese Ministry of Education (No. 107018).     

The ring authenticated encryption scheme – How to provide a clue wisely

Though cryptography is being used more and more widely in reality, it seems that there exists no scheme or a concatenation of some existing schemes that could deal soundly with such practical situations as providing a clue, where the provider of the clue may want to reserve his beneficial rights while keeping his identity secret. To address this problem, inspired by the two notions of the ring signature and the authenticated encryption signature, we propose a new type of authenticated encryption scheme, which we call the ring authenticated encryption scheme, which can enable any member of a group of persons to provide a clue to some designated recipient wisely.     

Catching two rabbits: adaptive real‐time support for embedded Linux

The trend of digital convergence makes multitasking common in many digital electronic products. Some applications in those systems have inherent real‐time properties, while many others have few or no timeliness requirements. Therefore the embedded Linux kernels, which are widely used in those devices, provide real‐time features in many forms. However, providing real‐time scheduling usually induces throughput degradation in heavy multitasking due to the increased context switches. Usually the throughput degradation becomes a critical problem, since the performance of the embedded processors is generally limited for cost, design and energy efficiency reasons. This paper proposes schemes to lessen the throughput degradation, which is from real‐time scheduling, by suppressing unnecessary context switches and applying real‐time scheduling mechanisms only when it is necessary. Also the suggested schemes enable the complete priority inheritance protocol to prevent the well‐known priority inversion problem. We evaluated the effectiveness of our approach with open‐source benchmarks. By using the suggested schemes, the throughput is improved while the scheduling latency is kept same or better in comparison with the existing approaches. Copyright © 2008 John Wiley & Sons, Ltd.     

A modified advancing layers mesh generation for thin three-dimensional objects with variable thickness

A method of generating modified advancing layers mesh is proposed. In this paper the mesh generation process of semi-unstructured prismatic/tetrahedral mesh is presented for relatively thin three-dimensional geometries with variable thickness, as in the case of injection molding analysis. Prismatic meshes are generated by offsetting initial surface triangular meshes. During the mesh generation process, mesh quality is efficiently improved with the use of a new node relocation method. Finally, tetrahedral meshes are automatically generated in the rest of the domain. The mesh generating capability of the proposed algorithm is demonstrated with the several practical test cases.     

Impact of bandwidth request schemes for Best-Effort traffic in IEEE 802.16 networks

In IEEE 802.16 networks, bandwidth request–grant schemes are employed for reducing data collision and supporting various QoS requirements. In this paper, we investigate the impact of such schemes on Best-Effort (BE) traffic. We examine three candidate schemes. In the first scheme, each Subscribe Station (SS) attempts to request bandwidth in every frame to reduce delay. In the second scheme, the number of bandwidth request is limited to avoid collisions in bandwidth request. In the third scheme, a base station allocates bandwidth to each SS based on the measured sending rate without explicit bandwidth request. We quantitatively analyze the performance of these schemes in terms of the collision rate and buffer length. We also present a simulation study to validate our analysis and to observe the impact of these schemes on BE traffic. This paper shows that IEEE 802.16 networks can be effectively managed through appropriate bandwidth request schemes. It is also shown that bandwidth allocation without request can be an alternative for increasing utilization.     

Tensor-Based AAM with Continuous Variation Estimation: Application to Variation-Robust Face Recognition

The active appearance model (AAM) is a well-known model that can represent a non-rigid object effectively. However, the fitting result is often unsatisfactory when an input image deviates from the training images due to its fixed shape and appearance model. To obtain more robust AAM fitting, we propose a tensor-based AAM that can handle a variety of subjects, poses, expressions, and illuminations in the tensor algebra framework, which consists of an image tensor and a model tensor. The image tensor estimates image variations such as pose, expression, and illumination of the input image using two different variation estimation techniques: discrete and continuous variation estimation. The model tensor generates variation-specific AAM basis vectors from the estimated image variations, which leads to more accurate fitting results. To validate the usefulness of the tensor-based AAM, we performed variation-robust face recognition using the tensor-based AAM fitting results. To do, we propose indirect AAM feature transformation. Experimental results show that tensor-based AAM with continuous variation estimation outperforms that with discrete variation estimation and conventional AAM in terms of the average fitting error and the face recognition rate.     

FDF: Frequency detection-based filtering of scanning worms

In this paper, we propose a simple algorithm for detecting scanning worms with high detection rate and low false positive rate. The novelty of our algorithm is inspecting the frequency characteristic of scanning worms instead of counting the number of suspicious connections or packets from a monitored network. Its low complexity allows it to be used on any network-based intrusion detection system as a real-time detection module for high-speed networks.Our algorithm need not be adjusted to network status because its parameters depend on application types, which are generally and widely used in any networks such as web and P2P services. By using real traces, we evaluate the performance of our algorithm and compare it with that of SNORT. The results confirm that our algorithm outperforms SNORT with respect to detection rate and false positive rate.