Let G be a connected graph in which we designate a vertex or a block (a biconnected component) as the center of G. For each cut-vertex v, let G_v be the connected subgraph induced from G by v and the vertices that will be separated from the center by removal of v, where v is designated as the root of G_v. We consider the set R of all such rooted subgraphs in G, and assign an integer, called an index, to each of the subgraphs so that two rooted subgraphs in R receive the same indices if and only if they are isomorphic under the constraint that their roots correspond each other. In this paper, assuming a procedure for computing a signature of each graph in a class of biconnected graphs, we present a framework for computing indices to all rooted subgraphs of a graph G with a center which is composed of biconnected components from . With this framework, we can find indices to all rooted subgraphs of a outerplanar graph with a center in linear time and space.

In this paper, a study on discrete-time coined quantum walks on the line is presented. Clear mathematical foundations are still lacking for this quantum walk model. As a step toward this objective, the following question is being addressed: Given a graph, what is the probability that a quantum walk arrives at a given vertex after some number of steps? This is a very natural question, and for random walks it can be answered by several different combinatorial arguments. For quantum walks this is a highly non-trivial task. Furthermore, this was only achieved before for one specific coin operator (Hadamard operator) for walks on the line. Even considering only walks on lines, generalizing these computations to a general SU(2) coin operator is a complex task. The main contribution is a closed-form formula for the amplitudes of the state of the walk (which includes the question above) for a general symmetric SU(2) operator for walks on the line. To this end, a coin operator with parameters that alters the phase of the state of the walk is defined. Then, closed-form solutions are computed by means of Fourier analysis and asymptotic approximation methods. We also present some basic properties of the walk which can be deducted using weak convergence theorems for quantum walks. In particular, the support of the induced probability distribution of the walk is calculated. Then, it is shown how changing the parameters in the coin operator affects the resulting probability distribution.

Given a collection of k sets consisting of a total of n points in the plane, the distance from any point in the plane to each of the sets is defined to be the minimum among distances to each point in the set. The farthest-color Voronoi diagram is defined as a generalized Voronoi diagram of the k sets with respect to the distance functions for each of the k sets. The combinatorial complexity of the diagram is known to be Θ(kn) in the worst case. This paper initiates a study on farthest-color Voronoi diagrams having O(n) complexity. We introduce a realistic model, which defines a certain class of the diagrams with desirable geometric properties observed. We finally show that the farthest-color Voronoi diagrams under the model have linear complexity.

We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing only one edge color assignment at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. Ito, Kamiski and Demaine gave a sufficient condition so that any list edge-coloring of a tree can be transformed into any other. In this paper, we give a new sufficient condition which improves the known one. Our sufficient condition is best possible in some sense. The proof is constructive, and yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree with n vertices via O(n²) recoloring steps. We remark that the upper bound O(n²) on the number of recoloring steps is tight, because there is an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires Ω(n²) recoloring steps.

In the present paper, we consider fully asynchronous parallelism in membrane computing, and propose two asynchronous P systems for the satisfiability (SAT) and Hamiltonian cycle problem. We first propose an asynchronous P system that solves SAT with n variables and m clauses, and show that the proposed P system computes SAT in O(mn2ⁿ) sequential steps or O(mn) parallel steps using O(mn) kinds of objects. We next propose an asynchronous P system that solves the Hamiltonian cycle problem with n nodes, and show that the proposed P system computes the problem in O(n!) sequential steps or O(n²) parallel steps using O(n²) kinds of objects.

We show a technique for estimating an upper bound of the Gowers norm of modulo functions over prime fields, which reduces the estimation to the greatest common divisor of some periodic sequences. This estimation provides inapproximability of the modulo functions by low-degree polynomials over prime fields, which is a generalization of Viola and Wigderson's result in the case of the binary field.

This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly n vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3],[6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all “ordered” trees with n vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with n vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k=1,2, ...,n-1, we can also generate all rooted trees with exactly n vertices.

The k-edge-connectivity augmentation problem with bipartition constraints (kECABP, for short) is defined by “Given an undirected graph G=(V, E) and a bipartition π = {V_B, V_W} of V with V_B ∩ V_W = ∅, find an edge set E_f of minimum cardinality, consisting of edges that connect V_B and V_W, such that G'=(V, E ∪ E_f) is k-edge-connected.” The problem has applications for security of statistical data stored in a cross tabulated table, and so on. In this paper we propose a fast algorithm for finding an optimal solution to (σ + 1)ECABP in O(|V||E| + |V²|log |V|) time when G is σ-edge-connected (σ > 0), and show that the problem can be solved in linear time if σ ∈ {1, 2}.

As a giant in open source community, OpenOffice.org has become the most popular office suite within Linux community. But OpenOffice.org is relatively slow while loading documents. Research shows that the most time consuming part is importing one page of whole document. If there are many pages in a document, the accumulation of time consumed can be astonishing. Therefore, this paper proposes a solution, which has improved the speed of loading documents through asynchronous importing mechanism: a document is not imported as a whole, but only part of the document is imported at first for display, then mechanism in the background is started to asynchronously import the remaining parts, and insert it into the drawing queue of OpenOffice.org for display. In this way, the problem can be solved and users don't have to wait for a long time. Application start-up time testing tool has been used to test the time consumed in loading different pages of documents before and after optimization of OpenOffice.org, then, we adopt the regression theory to analyse the correlation between the page number of documents and the loading time. In addition, visual modeling of the experimental data are acquired with the aid of matlab. An obvious increase in loading speed can be seen after a comparison of the time consumed to load a document before and after the solution is adopted. And then, using Microsoft Office compared with the optimized OpenOffice.org, their loading speeds are almost same. The results of the experiments show the effectiveness of this solution.

As supercomputers increase in size, the mean time between failures (MTBF) of a system becomes shorter, and the reliability problem of supercomputers becomes more and more serious. MPI is currently the de facto standard used to build high-performance applications, and researches on the fault tolerance methods of MPI are always hot topics. However, due to the characteristics of MPI programs, most current checkpointing methods for MPI programs need to modify the MPI library (even operating system), or implement a complicated protocol by logging lots of messages. In this paper, we carry forward the idea of Application-Level Checkpointing (ALC). Based on the general fact that programmers are familiar with the communication characteristics of applications, we have developed BC-ALC, a new portable blocking coordinated ALC for MPI programs. BC-ALC neither modifies the MPI library (even operating system) nor logs any message. It implements coordination only by the Barrier operations instead of any complicated protocol. Furthermore, in order to reduce the cost of fault-tolerance, we reduce the synchronization range of the barrier, and design WBC-ALC, a weak blocking coordinated ALC utilizing group synchronization instead of global synchronization based on the communication relationship between processes. We also propose a fault-tolerance framework developed on top of WBC-ALC and discuss an implementation of it. Experimental results on NPB3.3-MPI benchmarks validate BC-ALC and WBC-ALC, and show that compared with BC-ALC, the average coordination time and the average backup time of a single checkpoint in WBC-ALC are reduced by 44.5% and 5.7% respectively.

While the Secure Socket Layer or Transport Layer Security (SSL/TLS) is assumed to provide secure communications over the Internet, many web applications utilize basic or digest authentication of Hyper Text Transport Protocol (HTTP) over SSL/TLS. Namely, in the scheme, there are two different authentication schemes in a session. Since they are separated by a layer, these are not convenient for a web application. Moreover, the scheme may also cause problems in establishing secure communication. Then we provide a scheme of authentication binding between SSL/TLS and HTTP without modifying SSL/TLS protocols and its implementation, and we show the effectiveness of our proposed scheme.

In the present paper, we address the problem of extrapolating group proximities from member relations, which we refer to as the group proximity problem. We assume that a relational dataset consists of several groups and that pairwise relations of all members can be measured. Under these assumptions, the goal is to estimate group proximities from pairwise relations. In order to solve the group proximity problem, we present a method based on embedding and distribution mapping, in which all relational data, which consist of pairwise dissimilarities or dissimilarities between members, are transformed into vectorial data by embedding methods. After this process, the distributions of the groups are obtained. Group proximities are estimated as distances between distributions by distribution mapping methods, which generate a map of distributions. As an example, we apply the proposed method to document and bacterial flora datasets. Finally, we confirm the feasibility of using the proposed method to solve the group proximity problem.

We propose a new method, called Subclass-oriented Dimensionality Reduction with Pairwise Constraints (SODRPaC), for dimensionality reduction. In a high dimensional space, it is common that a group of data points with one class may scatter in several different groups. Current linear semi-supervised dimensionality reduction methods would fail to achieve fair performances, as they assume two data points linked by a must-link constraint are close each other, while they are likely to be located in different groups. Inspired by the above observation, we classify the must-link constraint into two categories, which are the inter-subclass must-link constraint and the intra-subclass must-link constraint, respectively. We carefully generate cannot-link constraints by using must-link constraints, and then propose a new discriminant criterion by employing the cannot-link constraints and the compactness of shared nearest neighbors. The manifold regularization is also incorporated in our dimensionality reduction framework. Extensive experiments on both synthetic and practical data sets illustrate the effectiveness of our method.

Link prediction in social networks, such as friendship networks and coauthorship networks, has recently attracted a great deal of attention. There have been numerous attempts to address the problem of link prediction through diverse approaches. In the present paper, we focus on the temporal behavior of the link strength, particularly the relationship between the time stamps of interactions or links and the temporal behavior of link strength and how link strength affects future link evolution. Most previous studies have not sufficiently discussed either the impact of time stamps of the interactions or time stamps of the links on link evolution. The gap between the current time and the time stamps of the interactions or links is also important to link evolution. In the present paper, we introduce a new time-aware feature, referred to as time score, that captures the important aspects of time stamps of interactions and the temporality of the link strengths. We also analyze the effectiveness of time score with different parameter settings for different network data sets. The results of the analysis revealed that the time score was sensitive to different networks and different time measures. We applied time score to two social network data sets, namely, Facebook friendship network data set and a coauthorship network data set. The results revealed a significant improvement in predicting future links.

We have developed a portable NIRS-based optical BCI system that features a non-invasive, facile probe attachment and does not require muscle movement to control the target devices. The system consists of a 2-channel probe, a signal-processing unit, and an infrared-emission device, which measures the blood volume change in the participant's prefrontal cortex in a real time. We use the threshold logic as a switching technology, which transmits a control signal to a target device when the electrical waveforms exceed the pre-defined threshold. Eight healthy volunteers participated in the experiments and they could change the television channel or control the movement of a toy robot with average switching times of 11.5 ± 5.3 s and the hit rate was 83.3%. These trials suggest that this system provides a novel communication aid for people with motor disabilities.

In this paper, we propose N-Dimensional (ND) Tensor Supervised Neighborhood Embedding (ND TSNE) for discriminant feature representation, which is used for view-based object recognition. ND TSNE uses a general N^th order tensor discriminant and neighborhood-embedding analysis approach for object representation. The benefits of ND TSNE include: (1) a natural way of representing data without losing structure information, i.e., the information about the relative positions of pixels or regions; (2) a reduction in the small sample size problem, which occurs in conventional supervised learning because the number of training samples is much less than the dimensionality of the feature space; (3) preserving a neighborhood structure in tensor feature space for object recognition and a good convergence property in training procedure. With Tensor-subspace features, the random forests is used as a multi-way classifier for object recognition, which is much easier for training and testing compared with multi-way SVM. We demonstrate the performance advantages of our proposed approach over existing techniques using experiments on the COIL-100 and the ETH-80 datasets.

A new approach to speech feature estimation under noise circumstances is proposed in this paper. It is used in noise-robust continuous speech recognition (CSR). As the noise robust techniques in isolated word speech recognition, the running spectrum analysis (RSA), the running spectrum filtering (RSF) and the dynamic range adjustment (DRA) methods have been developed. Among them, only RSA has been applied to a CSR system. This paper proposes an extended DRA for a noise-robust CSR system. In the stage of speech recognition, a continuous speech waveform is automatically assigned to a block defined by a short time length. The extended DRA is applied to these estimated blocks. The average recognition rate of the proposed method has been improved under several different noise conditions. As a result, the recognition rates are improved up to 15% in various noises with 10 dB SNR.

In the task of face recognition, a challenging issue is the one sample problem, namely, there is only one training sample per person. Principal component analysis (PCA) seeks a low-dimensional representation that maximizes the global scatter of the training samples, and thus is suitable for one sample problem. However, standard PCA is sensitive to the outliers and emphasizes more on the relatively distant sample pairs, which implies that the close samples belonging to different classes tend to be merged together. In this paper, we propose two-stage block-based whitened PCA (TS-BWPCA) to address this problem. For a specific probe image, in the first stage, we seek the K-Nearest Neighbors (K-NNs) in the whitened PCA space and thus exclude most of samples which are distant to the probe. In the second stage, we maximize the “local” scatter by performing whitened PCA on the K nearest samples, which could explore the most discriminative information for similar classes. Moreover, block-based scheme is incorporated to address the small sample problem. This two-stage process is actually a coarse-to-fine scheme that can maximize both global and local scatter, and thus overcomes the aforementioned shortcomings of PCA. Experimental results on FERET face database show that our proposed algorithm is better than several representative approaches.

Large-scale adoption of electronic healthcare applications requires semantic interoperability. The new proposals propose an advanced (multi-level) DBMS architecture for repository services for health records of patients. These also require query interfaces at multiple levels and at the level of semi-skilled users. In this regard, a high-level user interface for querying the new form of standardized Electronic Health Records system has been examined in this study. It proposes a step-by-step graphical query interface to allow semi-skilled users to write queries. Its aim is to decrease user effort and communication ambiguities, and increase user friendliness.

Magnetic particle imaging (MPI), in which the nonlinear interaction between internally administered magnetic nanoparticles (MNPs) and electromagnetic waves irradiated from outside of the body is utilized, has attracted attention for its potential to achieve early diagnosis of diseases such as cancer. In MPI, the local magnetic field distribution is scanned, and the magnetization signal from MNPs within a selected region is detected. However, the signal sensitivity and image resolution are degraded by interference from magnetization signals generated by MNPs outside of the selected region, mainly because of imperfections (limited gradients) in the local magnetic field distribution. Here, we propose new methods based on correlation information between the observed signal and the system function–defined as the interaction between the magnetic field distribution and the magnetizing properties of MNPs. We performed numerical analyses and found that, although the images were somewhat blurred, image artifacts could be significantly reduced and accurate images could be reconstructed without the inverse-matrix operation used in conventional image reconstruction methods.

In this letter, we introduce a novel patch sampling strategy for the task of image classification, which is fundamentally different from current patch sampling strategies. A top-down guidance learned from training images is used to guide patch sampling towards informative regions. Experiment results show that this approach achieved noticeable improvement over baseline patch sampling strategies for the classification of both object categories and scene categories.

This work examines energy trajectory and voice quality measurements, in addition to conventional formant and duration properties, to classify tense and lax vowels in English. Tense and lax vowels are produced with differing articulatory configurations which can be identified by measuring acoustic cues such as energy peak location, energy convexity, open quotient and spectral tilt. An analysis of variance (ANOVA) is conducted, and dialect effects are observed. An overall 85.2% classification rate is obtained using the proposed features on the TIMIT database, resulting in improvement over using only conventional acoustic features. Adding the proposed features to widely used cepstral features also results in improved classification.

In this paper, we propose a way to improve the classification performance of support vector machines (SVMs), especially for speech and music frames within a selectable mode vocoder (SMV) framework. A myriad of techniques have been proposed for SVMs, and most of them are employed during the training phase of SVMs. Instead, the proposed algorithm is applied during the test phase and works with existing schemes. The proposed algorithm modifies a kernel parameter in the decision function of SVMs to alter SVM decisions for better classification accuracy based on the previous outputs of SVMs. Since speech and music frames exhibit strong inter-frame correlation, the outputs of SVMs can guide the kernel parameter modification. Our experimental results show that the proposed algorithm has the potential for adaptively tuning classifications of support vector machines for better performance.

To reconstruct low-resolution facial photographs which are in focus and without motion blur, a novel algorithm based on local similarity preserving is proposed. It is based on the theories of local manifold learning. The innovations of the new method include mixing point-based entropy and Euclidian distance to search for the nearest points, adding point-to-patch degradation model to restrict the linear weights and compensating the fusing patch to keep energy coherence. The compensation reduces the algorithm dependence on training sets and keeps the luminance of reconstruction constant. Experiments show that our method can effectively reconstruct 1612 images with the magnification of 88 and the 3224 facial photographs in focus and without motion blur.

The general method for estimating phrase translation probabilities consists of sequential processes: word alignment, phrase pair extraction, and phrase translation probability calculation. However, during this sequential process, errors may propagate from the word alignment step through the translation probability calculation step. In this paper, we propose a new method for estimating phrase translation probabilities that reduce the effects of error propagation. By considering the semantic recoverability of phrase retranslation, our method identifies incorrect phrase pairs that have propagated from alignment errors. Furthermore, we define retranslation similarity which represents the semantic recoverability of phrase retranslation, and use this when computing translation probabilities. Experimental results show that the proposed phrase translation estimation method effectively prevents a PBSMT system from selecting incorrect phrase pairs, and consistently improves the translation quality in various language pairs.