Título:
QUBO formulation for the Snake-in-the-box and Coil-in-the-box problems.
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Fuidio, Federico
Canale, Eduardo
Sotelo, Rafael
Canale, Eduardo
Sotelo, Rafael
Tutor:
Tipo de documento:
Preprint
Editor:
Palabras clave:
QUBO
Quantum Annealer
Snake in the box
Coil in the box
Maximum common induced sub-graph problem
Quantum Annealer
Snake in the box
Coil in the box
Maximum common induced sub-graph problem
Descriptores:
Año de publicación:
2024
Contenido:
Resumen:
This paper present the first QUBO formulations for the Snake-in-the-box (SITB) and Coil-in-the-box (CITB) problems. Both formulations are also capable of solving the NP-Hard problems of Maximum induced path and Maximum induced cylce respectively. In the process we also found a new QUBO formulation for the Maximum Common Induced Sub-graph problem. We proved the correctness of our formulations for the SITB, CITB and Maximum Common Sub-graph problem, and tested the formulations of the SITB and CITB in both classical and quantum solvers, being able to get the best solution for up to 5 dimensions.
Descripción:
metadata.articulos.dc.description.uri:
Editorial:
EN:
Financiadores:
Citación:
Fuidio, F., Canale, E. y Sotelo, R. QUBO formulation for the Snake-in-the-box and Coil-in-the-box problems [Preprint]. DOI: 10.48550/arXiv.2409.04476.
Citación:
metadata.articulos.cc.license.name:
ISBN:
e-ISBN:
ISSN:
ISMN:
Otros identificadores:
Cobertura geográfica:
Cobertura temporal:
Departamento académico:
Grupo de investigación:
Licencia:
Licencia Creative Commons Atribución (CC - By 4.0)
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| FCS24.pdf | Preprint | 194.07 KB | Adobe PDF |