QUBO formulations for the graph isomorphism problem and related problems

DOI10.1016/j.tcs.2017.04.016zbMath1382.68081OpenAlexW2587690780MaRDI QIDQ1682856

Richard Hua, Cristian S. Calude, Michael J. Dinneen

Publication date: 6 December 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.04.016

zbMATH Keywords

subgraph isomorphism problemadiabatic quantum computinggraph isomorphism problemquadratic unconstrained binary optimizationChimera graph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (6)

Graph isomorphism and Gaussian boson sampling ⋮ QUBO formulations for the graph isomorphism problem and related problems ⋮ Quantum Annealing versus Digital Computing ⋮ A QUBO formulation for the tree containment problem ⋮ Quantum solutions for densest \(k\)-subgraph problems ⋮ Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem

Uses Software

• Python

Cites Work

• Subgraph isomorphism, matching relational structures and maximal cliques
• QUBO formulations for the graph isomorphism problem and related problems
• Graph isomorphism in quasipolynomial time [extended abstract]
• Unnamed Item
• Unnamed Item

This page was built for publication: QUBO formulations for the graph isomorphism problem and related problems