This paper proposes a method for searching for graphs in the database which are contained as subgraphs by a given query. In the proposed method, the search index does not require any knowledge of the query set or the frequent subgraph patterns. In conventional techniques, enumerating and selecting frequent subgraph patterns is computationally expensive, and the distribution of the query set must be known in advance. Subsequent changes to the query set require the frequent patterns to be selected again and the index to be reconstructed. The proposed method overcomes these difficulties through graph coding, using a tree structured index that contains infrequent subgraph patterns in the shallow part of the tree. By traversing this code tree, we are able to rapidly determine whether multiple graphs in the database contain subgraphs that match the query, producing a powerful pruning or filtering effect. Furthermore, the filtering and verification steps of the graph search can be conducted concurrently, rather than requiring separate algorithms. As the proposed method does not require the frequent subgraph patterns and the query set, it is significantly faster than previous techniques; this independence from the query set also means that there is no need to reconstruct the search index when the query set changes. A series of experiments using a real-world dataset demonstrate the efficiency of the proposed method, achieving a search speed several orders of magnitude faster than the previous best.

This paper proposes a regulated transport network design algorithm for IP over a dense wavelength division multiplex (DWDM) network. When designing an IP over DWDM network, the network operator should consider not only cost-effectiveness and physical constraints such as wavelength colors and chromatic dispersion but also operational policies such as resilience, quality, stability, and operability. For considering the above polices, we propose to separate the network design algorithm based on a geographical resolution; the policy-based regulated intra-area is designed based on this resolution, and the cost-optimal inter-area is then designed separately, and finally merged. This approach does not necessarily yield a strict optimal solution, but it covers network design work done by humans, which takes a vast amount of time and requires a high skill level. For efficient geographical resolution, we also present fast graph mining algorithm, which can solve NP-hard subgraph isomorphism problem within the practical time. We prove the sufficiency of the resulting network design for the above polices by visualizing the topology, and also prove that the penalty of applying the approach is trivial.

We formally define the mobile agent allocation problem from a system-wide viewpoint and then prove that it is strongly NP-complete even if each agent communicates only with two agents. This is the first formal definition for scheduling mobile agents from the viewpoint of load balancing, which enables us to discuss its properties on a rigorous basis. The problem is recognized as preemptive scheduling with independent tasks that require mutual communication. The result implies that almost all subproblems of mobile agent allocation, which require mutual communication of agents, are strongly NP-complete.

Efficient content-based retrieval of complex images is a challenging task since the detected object may appear in various scale, rotation and orientation with a wide variety of background colors and forms. In this paper, we propose a novel representation of objects with multiple colors, the spatial neighborhood-adjacency graph(SNAG), which can serve as a basis for detecting object by color contents from the candidate image. The SNAG consists of a set of main-vertices and two sets of edges. Each main-vertex represents a single color region of multi-colored object, and edges are divided into two classes: Neighborhood edges representing neighborhood relationship between two main-vertices with similar color, and adjacency edges representing adjacency relationship between a main-vertex and another vertex with different color. By investigating whether SNAG of object image is an isomorphic subgraph of SNAG of a candidate image, we can determine whether the similar object exists in the candidate image. In addition, we have also applied the proposed approach to a range of different object detection problems involving complex background, and effectiveness has been proved.

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 considers the problem of finding a largest common subgraph of graphs, which is an important problem in chemical synthesis. It is known that the problem is NP-hard even if graphs are restricted to planar graphs of vertex degree at most three. By the way, a graph is called an almost tree if E(B)V(B)+ K holds for every block B where K is a constant. In this paper, a polynomial time algorithm for finding a largest common subgraph of two graphs which are connected, almost trees and of bounded vertex degree. The algorithm is an extension of a subtree isomorphism algorithm which is based on dynamic programming. Moreover, it is shown that the degree bound is essential. That is, the problem of finding a largest common subgraph of two connected almost trees is proved to be NP-hard for any K0 if degree is not bounded. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem.

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.