Uma nova abordagem para dividir instâncias do Discretizable Molecular Distance Geomety Problem usando gaps

Abstract

Motivado pelo Parallel BP, que divide instâncias do Discretizable Molecular Distance Geometry Problem (DMDGP) em sub-instâncias com o mesmo número de vértices cada, este trabalho propõe duas divisões mais flexíveis, baseadas nas informações de distâncias disponíveis. Tais abordagens foram desenvolvidas na tentativa de separar as partes com rápida determinação das partes mais lentas, em relação ao custo computacional do Algoritmo Branch & Prune, utilizando os chamados gaps. Resultados compuacionais preliminares indicam que abordagem é mais eficiente.