Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao https://doi.org/10.1...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
https://doi.org/10.1109/icce-b...
Article . 2019 . Peer-reviewed
License: STM Policy #29
Data sources: Crossref
versions View all 1 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Efficient Ising Model Mapping for Induced Subgraph Isomorphism Problems Using Ising Machines

Authors: Masashi Tawada; Nozomu Togawa; Junya Arai; Natsuhito Yoshimura; Hiroyuki Uchiyama; Shu Tanaka; Satoshi Yagi;

Efficient Ising Model Mapping for Induced Subgraph Isomorphism Problems Using Ising Machines

Abstract

Ising machines have attracted attention as they are expected to solve combinatorial optimization problems at high speed with Ising models corresponding to those problems. An induced subgraph isomorphism problem is one of the decision problems, which determines whether a specific graph structure is included in a whole graph or not. The problem can be represented by equality constraints. By using the penalty functions correspond to the equality constraints, we can utilize an Ising machine to the induced subgraph isomorphism problem. The induced subgraph isomorphism problem can be seen in many practical problems, for example, finding out a particular malicious circuit in a device or particular network structure of chemical bonds in a compound. However, due to the limitation of the number of spin variables in the current Ising machines, reducing the number of spin variables is a major concern. Here, we propose an efficient Ising model mapping method to solve the induced subgraph isomorphism problem by Ising machines. Our proposed method theoretically solves the induced subgraph isomorphism problem. Furthermore, the number of spin variables in the Ising model generated by our proposed method is theoretically smaller than that of the conventional method. Experimental results demonstrate that our proposed method can successfully solve the induced subgraph isomorphism problem using the Isingmodel based simulated annealing.

Related Organizations
  • BIP!
    Impact byBIP!
    citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    8
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
citations
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
8
Top 10%
Average
Top 10%
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!