Data Dependent Circuit for Subgraph Isomorphism Problem
スポンサーリンク
概要
- 論文の詳細を見る
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 hardscale 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.
- 社団法人電子情報通信学会の論文
- 2003-05-01
著者
-
Ichikawa Shuichi
Department Of Knowledge-based Information Engineering Toyohashi University Of Technology
-
Ichikawa Shuichi
Department Of Internal Medicine Cardiovascular Hospital Of Central Japan (kitakanto Cardiovascular H
-
Ichikawa S
Toyohashi Univ. Technol. Toyohashi‐shi Jpn
-
Yamamoto Shoji
Department Of Biological Chemistry And Crest (core Research For Educational Science And Technology)
-
Yamamoto Shoji
Department Of Knowledge-based Information Engineering Toyohashi University Of Technology
-
Ichikawa Shuichi
Department Of Internal Medicine Cardiovascular Hospital Of Central Japan
関連論文
- Ten-Year Patency and Factors Causing Restenosis After Endovascular Treatment of Iliac Artery Lesions
- PJ-729 Elevated Arterial Stiffness in Postmenopausal Women with Osteoporosis(Atherosclerosis, clinical-15 (H) PJ123,Poster Session (Japanese),The 70th Anniversary Annual Scientific Meeting of the Japanese Circulation Society)
- Effects of Raloxifene on Brachial Arterial Endothelial Function, Carotid Wall Thickness, and Arterial Stiffness in Osteoporotic Postmenopausal Women
- PJ-436 Impaired Vascular Endothelial Function in Postmenopausal Women with Osteoporosis(Atherosclerosis, clinical-13, The 71st Annual Scientific Meeting of the Japanese Circulation Society)
- PJ-435 Raloxifene is Effective for Reducing Carotid Artery Wall Thickness and Increasing Bone Mineral Density in Postmenopausal Women with Osteoporosis(Atherosclerosis, clinical-13, The 71st Annual Scientific Meeting of the Japanese Circulation Society)
- Effect of Transdermal Hormone Replacement Therapy on Carotid Artery Wall Thickness and Levels of Vascular Inflammatory Markers in Postmenopausal Women
- Design and Evaluation of Data-Dependent Hardware for AES Encryption Algorithm(VLSI Systems)
- Pressure Effects on an S = 1 Haldane Compound Ni(C_5H_N_2)_2N_3(PF_6)
- Pressure Effects on an S=1 Haldane Compound Ni(C_5H_N_2)_2N_3(PF_6)
- Quantum Phase Competition in Antiferromagnetic Spin-1 Ladders
- Re-Entrant Quantum Phase Transitions in Antiferromagnetic Spin-1 Ladders(Condensed Matter : Electronic Structure, Electrical, Mgagnetic and Optical Properties)
- Magnetization Plateau in One-Dimensional Quantum Ferrimagnets
- Diversification of Processors Based on Redundancy in Instruction Set
- Prevalence and risk factors for renal artery stenosis and chronic kidney disease in Japanese patients with peripheral arterial disease
- The Evaluation of Davidson's Digital Signature Scheme (Cryptography and Information Security)
- Design and Evaluation of Hardware Pseudo-Random Number Generator MT19937(VLSI Systems)
- Resonating Hartree-Fock Theory of the One Dimensional Hubbard Model. : II. Breather Fluctuations in the Strong Correlation Regime
- Superpolaron Model for Metallic Polyacetylene
- Resonating Hartree-Fock Theory of the One Dimensional Hubbard Model.I.Quantum Fluctuations by SDW Solitons and Breathers
- Redundancy in Instruction Sequences of Computer Programs(Information Hiding, Cryptography and Information Security)
- Evidence for Multimagnon-Mediated Nuclear Spin Relaxation in the Intertwining Double-Chain Ferrimagnet Ca_3Cu_3(PO_4)_4(Condensed matter: electronic structure and electrical, magnetic, and optical properties)
- Long-Term Effects of Olmesartan, an Ang II Receptor Antagonist, on Blood Pressure and the Renin-Angiotensin-Aldosterone System in Hypertensive Patients
- Numerical Simulation of the Proton Spin-Lattice Relaxation in Bimetallic Chain Compounds
- Spin Dynamics in Molecular Ring Nanomagnets : Significant Effect of Acoustic Phonons and Magnetic Anisotropies(Condensed matter: electronic structure and electrical, magnetic, and optical properties)
- Effects of raloxifene on the renin-angiotensin-aldosterone system and blood pressure in hypertensive and normotensive osteoporotic postmenopausal women
- Molecular Cloning and Genomic Analysis of Mouse Glucuronyltransferase Involved in Biosynthesis of the HNK-1 Epitope
- Biosynthesis and Function of the Neural Specific Carbohydrate Antigen, HNK-1
- Orbital Optimization in the Resonating Hartree-Fock Approximation and Its Application to the One Dimensional Hubbard Model
- High-Temperature Effects on Antibody Response to Viral Antigen in Mice
- Magnetic Phase Diagram of Spin-1/2 Two-Leg Ladder with Four-Spin Ring Exchanges(Condensed matter: electronic structure and electrical, magnetic, and optical properties)
- Fermionic Description of Spin-Gap States of Antiferromagnetic Heisenberg Ladders in a Magnetic Field
- Trade-Offs in Custom Circuit Designs for Subgraph Isomorphism Problem(VLSI Systems)
- HNK-1糖鎖抗原の生合成に関わるグルクロン酸転移酵素
- An FPGA Implementation of Hard-Wired Sequence Control System Based On PLC Software
- Low-Temperature Properties of Quasi-One-Dimensional Molecule-Based Ferromagnets : Condensed Matter: Electronic Properties, etc.
- Data Dependent Circuit for Subgraph Isomorphism Problem
- The Design and Evaluation of Data-Dependent Hardware for Subgraph Isomorphism Problem(Recornfigurable Systems)(Reconfigurable Systems)
- Thermodynamic Properties of S=1 Antiferromagnetic Heisenberg Chains
- World-Line Monte Carlo Study of the Dispersion Relation of an S=1 Antiferromagnetic Heisenberg Chain
- Low-Energy Structure of Heisenberg Ferrimagnetic Spin Chains
- Ground-State Properties of S=1 Antiferromagnetic Heisenberg Chains with Bond Alternation
- Ground-State Properties of a Peierls–Hubbard Triangular Prism
- Competing Ground States of the New Class of Halogen-Bridged Metal Complexes : Condensed Matter: Electronic Properties, etc.
- Modified Spin-wave Description of the Nuclear Spin Relaxation in Ferrimagnetic Heisenberg Chains : Condensed Matter: Electronic Properties, etc.
- Quantum-Classical Crossover in Temperature Dependence of the Magnetic Susceptibility of Haldane System
- FPGA Implementation of Metastability-Based True Random Number Generator
- Soliton Excitations in Halogen-Bridged Mixed-Valence Binuclear Metal Complexes
- Quantum and Thermal Phase Transitions of Halogen-Bridged Binuclear Transition-Metal Complexes : Condensed Matter: Electronic Properties, etc.
- 18pHC-7 Photoinduced phase transitions in organic compounds based on the linear polybenzenoid structure
- 26aEJ-11 Photomanipulation of the ground state of a platinum-iodide square-prism compound
- 25aDA-13 Polarization effect on photoinduced phase transtions in a platimum-iodide square-prism compound
- Molecular Cloning and Genomic Analysis of Mouse Glucuronyltransferase Involved in Biosynthesis of the HNK-1 Epitope.