In this paper, we address the problem of finding a representation of a subtree distance, which is an extension of a tree metric. We show that a minimal representation is uniquely determined by a given subtree distance, and give an O(n2) time algorithm that finds such a representation, where n is the size of the ground set. Since a lower bound of the problem is Ω(n2), our algorithm achieves the optimal time complexity.

This paper presents a supervised method to classify a document at the sub-sentence level. Traditionally, sentiment analysis often classifies sentence polarity based on word features, syllable features, or N-gram features. A sentence, as a whole, may contain several phrases and words which carry their own specific sentiment. However, classifying a sentence based on phrases and words can sometimes be incoherent because they are ungrammatically formed. In order to overcome this problem, we need to arrange words and phrase in a dependency form to capture their semantic scope of sentiment. Thus, we transform a sentence into a dependency tree structure. A dependency tree is composed of subtrees, and each subtree allocates words and syllables in a grammatical order. Moreover, a sentence dependency tree structure can mitigate word sense ambiguity or solve the inherent polysemy of words by determining their word sense. In our experiment, we provide the details of the proposed subtree polarity classification for sub-opinion analysis. To conclude our discussion, we also elaborate on the effectiveness of the analysis result.

Tree structured data often appear in bioinformatics. For example, glycans, RNA secondary structures and phylogenetic trees usually have tree structures. Comparison of trees is one of fundamental tasks in analysis of these data. Various distance measures have been proposed and utilized for comparison of trees, among which extensive studies have been done on tree edit distance. In this paper, we review key results and our recent results on the tree edit distance problem and related problems. In particular, we review polynomial time exact algorithms and more efficient approximation algorithms for the edit distance problem for ordered trees, and approximation algorithms for the largest common sub-tree problem for unordered trees. We also review applications of tree edit distance and its variants to bioinformatics with focusing on comparison of glycan structures.

Broadcast encryption technology enables a sender to send information securely to a group of receivers excluding specified receivers over a broadcast channel. In this paper, we propose a new key-tree structure based on Rabin cryptosystem, and an access control scheme using the structure. We show the security of the access control scheme and construct a new broadcast encryption scheme based on it. The proposed broadcast encryption scheme is a modification of the complete subtree method and it reduces the number of keys a receiver stores to one. There have been proposed some modifications of the complete subtree method which minimize the number of keys for a receiver to one, and the most efficient one among them with respect to the computational overhead at receivers is based on RSA cryptosystem. The computational overhead at receivers in our scheme is around log2e times smaller than the most efficient previously proposed one, where e is a public exponent of RSA, and the proposed scheme is the most efficient among tree based one-key schemes. This property is examined by experimental results. Our scheme achieves this reduction in the computational overhead in exchange for an increase in the size of nonsecret memory by [log n * few (e.g. eight)] bits, where n is the total number of receivers.

Let G = (V,E) be a connected graph such that each edge e ∈ E and each vertex v ∈ V are weighted by nonnegative reals w(e) and h(v), respectively. Let r be a vertex designated as a root, and p be a positive integer. The minmax rooted-subtree cover problem (MRSC) asks to find a partition X = {X1,X2,...,Xp of V and a set of p subtrees T1,T2,...,Tp such that each Ti contains Xi∪{r} so as to minimize the maximum cost of the subtrees, where the cost of Ti is defined to be the sum of the weights of edges in Ti and the weights of vertices in Xi. Similarly, the minmax rooted-cycle cover problem (MRCC) asks to find a partition X = {X1,X2,...,Xp} of V and a set of p cycles C1,C2,...,Cp such that Ci contains Xi∪{r} so as to minimize the maximum cost of the cycles, where the cost of Ci is defined analogously with the MRSC. In this paper, we first propose a (3-2/(p+1))-approximation algorithm to the MRSC with a general graph G, and we then give a (6-4/(p+1))-approximation algorithm to the MRCC with a metric (G,w).

This paper deals with broadcast encryption schemes, in which a sender can send information securely to a group of receivers excluding some receivers over a broadcast channel. In this paper we propose modifications of the Complete Subtree (CS), the Subset Difference (SD) and the Layered Subset Difference (LSD) methods based on the Master Key Tree (MKT). Our modifications eliminate log N keys or labels from receivers' storage, in exchange for an increase in the computational overhead, where N is the total number of receivers. We also propose modifications of the SD and LSD methods by applying the Trapdoor One-way Permutation Tree (TOPT) which is originally proposed in order to modify the CS method. Our modifications based on TOPT also eliminate log N labels, and the computational cost is much smaller than MKT based methods.

The complete subtree (CS) method is one of the most well-known broadcast encryptions which do not enforce the receivers to keep "online." This paper is to reduce the size of secret information which must be stored in a terminal of the method. In the original CS method, the size of the secret information increases as the number of terminals increases. It is shown in this paper that, by making use of a one-way trapdoor permutation, we can make the size constant regardless of the number of terminals. The security of the proposed scheme is investigated, and detailed comparison with other similar schemes is presented. The proposed scheme is suitable for practical implementations of the CS method.

This paper presents a linear time algorithm for testing whether or not there is a path ,vm> of an undiercted tree T (|V(T)|n) that coincides with a string ss1sm (i.e., label(v1)label(vm)s1sm). Since any path of the tree is allowed, linear time substring matching algorithms can not be directly applied and a new method is developed. In the algorithm, O(n/m) vertices are selected from V(T) such that any path pf length more than m 2 must contain at least one of the selected vertices. A search is performed using the selected vertices as 'bases' and two tables of size O(m) are constructed for each of the selected vertices. A suffix tree, which is a well-known-data structure in string matching, is used effectively in the algorithm. From each of the selected vertices, a search is performed with traversing the suffix tree associated with s. Although the size of the alphabet is assumed to be bounded by a constant in this paper, the algorithm can be applied to the case of unbounded alphabets by increasing the time complexity to O(n log m).

This paper presents efficient algorithms for finding the largest tree S such that there are vertex disjoint subtrees S1, , S (k1) of T each of which is isomorphic to S and every leaf of T is a leaf of some Si. The algorithms are useful for learning a macro table.

It is known that the problem of finding a largest common subgraph is NP-hard for general graphs even if the number of input graphs is two. It is also known that the problem can be solved in polynomial time if the input is restricted to two trees. In this paper, a randomized parallel (an RNC) algorithm for finding a largest common subtree of two trees is presented. The dynamic tree contraction technique and the RNC minimum weight perfect matching algorithm are used to obtain the RNC algorithm. Moreover, an efficient NC algorithm is presented in the case where input trees are of bounded vertex degree. It works in O(log(n1)log(n2)) time using O(n1n2) processors on a CREW PRAM, where n1 and n2 denote the numbers of vertices of input trees. It is also proved that the problem is NP-hard if the number of input trees is more than two. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem of finding a largest common subtree of three trees.