Parallel implementations of TSP brute force algorithm

Authors

  • Rafael Almenara Ventura Alves UERJ
  • Cristiana Bentes Faculdade de Engenharia - UERJ
  • Maria Clicia S. Castro Instituto de Matemática e Estatística - UERJ

DOI:

https://doi.org/10.12957/cadinf.2024.79821

Abstract

The traveling salesman problem is a famous combinatorial optimization problem. Despite its great importance, there is no good exact solution for the generic case. Considering the existence not only of CPUs with many cores but also of GPUs allowing a more generic use and being more popular, this work tries to answer the question: up to what size of problem is it possible to solve in parallel through brute force in a timely manner? For this, implementations were developed in OpenMP, MPI, and CUDA.

Downloads

Download data is not yet available.

Published

2024-08-06

How to Cite

Almenara Ventura Alves, R., Bentes, C., & S. Castro, M. C. (2024). Parallel implementations of TSP brute force algorithm. Cadernos Do IME - Série Informática, 49, 97–112. https://doi.org/10.12957/cadinf.2024.79821

Issue

Section

Artigos

Most read articles by the same author(s)