Although the subgraph isomorphism problem has various important applications, it is generally NP-complete and difficult to solve. Though a custom computing circuit can reduce the execution time substantially, it requires considerable hardware resources and is inapplicable to large problems. This paper examines the feasibility of data dependent designs, which are particularly suitable to a Field Programmable Gate Array (FPGA). The data dependent approach drastically reduces hardware requirements. For graphs of 32 vertices, the average logic scale of data dependent circuits is only 5% of the corresponding data independent circuit. The data dependent circuit is estimated to be maximally 460 times faster than the software. Even if the circuit generation time is included, a data dependent circuit is estimated to be 2.04 times faster than software for graphs of 32 vertices. The performance gain would increase for larger graphs.

In this paper, we propose a new projector-based display which can perform the color simulator for print industry. The proposed color simulator can change the color of print by projecting the image onto the print. A color of print can be matched to the desired color by projecting the image which is calculated to minimize the color difference between the colors of target print and current print. This current print is measured by digital camera or digital scanner. Ideally, spectral camera or scanner is expected to be used for accurate color simulation on the current print, but it costs a lot for practical application. Therefore, in this paper, we compared two methods for color matching, one is the tristimulus-based method with XYZ tristimulus values and the other is the spectral-based method with spectral values. As the result of computer simulation, the average color difference ΔE *94 was 0.27 by the spectral-based method between the reflected radiance from the color of target print and the color of current print with projector, and the average color difference ΔE *94 was 2.09 by the tristimulus-based method. The efficiency of the proposed system is verified by the subjective evaluation between the target and current print with appropriate image projection.

Subgraph isomorphism problems have various important applications, while generally being NP-complete. Though Ullmann and Konishi proposed the custom circuit designs to accelerate subgraph isomorphism problem, they require many hardware resources for large problems. This study describes the design of data-dependent circuits for subgraph isomorphism problem with evaluation results on an actual FPGA platform. Data-dependent circuits are logic circuits specialized in specific input data. Such circuits are smaller and faster than the original circuit, although it is not reusable and involves circuit generation for each input. In the present study, the circuits were implemented on Xilinx XC2V3000 FPGA, and they successfully operated at a clock frequency 25 MHz. In the case of graphs with 16 vertices, the average execution time is about 7.0% of the software executed on an up-to-date microprocessor (Athlon XP 2600+ of 2.1 GHz clock). Even if the circuit generation time is included, data-dependent circuits are about 14.4 times faster than the software (for random graphs with 16 vertices). This performance advantage becomes larger for larger graphs. Two algorithms (Ullmann's and Konishi's) were examined, and the data-dependent approach was found to be equally effective for both algorithms. We also examined two types of input graph sets, and found that the data-dependent approach shows advantage in both cases.