Sobre o problema Euclidiano de Steiner no Rn

• Ano de defesa: 2017
• Autor(a) principal: Cruz, Luiz Felipe Rimola Ribeiro da
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Rio de Janeiro; Brasil; Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia; Programa de Pós-Graduação em Engenharia de Sistemas e Computação; UFRJ
• Palavras-chave em Português: Engenharia de Sistemas e Computação; Problema de Steiner para os vértices de um hipercubo; Otimização combinatória; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://hdl.handle.net/11422/8698

The Euclidean Steiner Problem (ESP) asks for a network of minimum length interconnecting a finite set of given points in Rn. The distances considered are Euclidean and it’s allowed to add additional points to decrease the overall length of the network. Problems of this nature are often found in several areas of mathematics, engineering, etc. In this work, we study the origins of ESP, their properties, complexity, and resolution methods. We conclude by analyzing a conjecture proposed in 1992 by Warren Smith on the application of this problem to the vertices of an n-dimensional hypercube, which has remained open since its publication.