Resumo
This work addresses the minimum subgraph diameter problem (MSDP), an NP-hard problem. Given a graph with lengths and costs associated with its edges, the MSDP consists in finding a spanning subgraph with total cost limited by a given budget, such that its diameter is minimum. We prove that there is no ?-approximation algorithm for the MSDP, for any constant ? unless P = NP. Moreover, we propose a benchmark of instances and present a computational study of mixed integer linear programming formulations and genetic algorithms for the MSDP.
Todos os trabalhos são de acesso livre, sendo que a detenção dos direitos concedidos aos trabalhos são de propriedade da Revista dos Trabalhos de Iniciação Científica da UNICAMP.