Posicionamento do Número Mínimo de Recursos que Maximizam Caminhos Vértice-Disjuntos em uma Rede de Topologia Arbitrária

O posicionamento de recursos em redes é um problema que encontra diversas variantes, desde o posicionamento de servidores na arquitetura tradicional cliente-servidor, passando pelo posicionamento de controladores em redes SDN, ou caches em redes CDN, entre vários outros. Este trabalho apresenta o problema de posicionar o número mínimo de recursos de modo a maximizar o número de caminhos vértice-disjuntos entre um recurso e seus clientes. Uma das contribuições do trabalho é a prova de que o problema de encontrar o número mínimo de recursos sob essas condições é NP-completo. Uma solução exata para o problema foi implementada e sua execução se mostrou viável em diversas redes de topologia arbitrária. Apresentamos os resultados comparando-os com o problema clássico em que é minimizada a soma das distâncias entre os clientes e seus recursos. Resultados experimentais avaliam o ganho de conectividade e o aumento da soma das distâncias quando a solução proposta é aplicada.