期刊名称：Relatórios de Pesquisa em Engenharia de Produção
电子版ISSN：1678-2399
出版年度：2008
卷号：8
出版社：Universidade Federal Fluminense (UFF)
摘要：The Hop-Constrained Minimum Spanning Tree Problem (HMSTP)arises in the design of centralized telecommunication networks with qual-ity of service constraints. We show that the HMSTP is equivalent to aSt einer Tree Problem (STP) in an adequate layered graph. We prove thatthe directed cut formulation for the STP defined in the layered graph,dominates the best previously known formulations for the HMSTP. Wethen show how cut s in the extended layered graph space can be projectedinto new families of cuts in the original design space. We also adaptthe proposed approach for the Diameter-Constrained Minimum SpanningTree Problem (DMSTP). Computational results with a branch-and-cutalgorithm show that the proposed method is significantly better than pre-viously known methods on both problems
其他摘要：O Problema da ′Arvore Geradora M′.nima com Restri.c.oes de Salto(HMST) surge no projeto de redes de comunica.c.ao centralizadas com re-stri.c.oes de qualidade de servi.co. Mostramos que o HMST ′e equivalentea um Problema da ′Arvore de Steiner (STP) sobre um grafo em camadas adequado. Provamos que a formula.c.ao de cortes direcionados para o STPaplicada ao grafo de camadas domina as melhores formula.c.oes conheci-das para o HMST. Tamb′em mostramos que cortes definidos sobre o grafoem camadas podem ser projetadas em novas fam′.lias de cortes no espa.code vari′aveis original. A abordagem tamb′em pode ser adaptada para oO Problema da ′Arvore Geradora M′.nima com Restri.c.oes de Di.ametro(DMST). Os resultados computacionais obtidos em ambos os problemass.ao significativamente melhores do que os obtidos com outros m′etodosconhecidos
关键词：Networks/Graphs: tree algorithms; Integer Programming:;formulations; cutting planes
其他关键词：Redes/Grafos: algoritmos para ′;arvores; Programa.;c.;ao;Inteira: formula.;c.;oes; planos de corte
