Adição, Complemento e Reversão de Arcos para Satisfazer Demandas de Conectividade em Digrafos
Autores
|
7151 |
519,3144
|
|
|
7152 |
519,3144
|
Informações:
Publicações do PESC
Considere um digrafo com custos associados a seus arcos e sujeito a operações de adição, complemento ou reversão de arcos. Quando aplicadas, as operações devem ser todas de um mesmo tipo, predefinido, e têm por objetivo obter um digrafo que atenda a certos requisitos de conectividade. Além disso, o custo total das operações efetuadas deve ser sempre o menor possível. Problemas desse tipo, muitas vezes NP-difíceis, são normalmente associados ao desenho de redes de telecomunicações ou de transportes. Nessas aplicações, o nível de conectividade imposto aos digrafos se reflete no grau de resiliência, flexibilidade ou eficiência de funcionamento que se quer obter para as redes. Formulações matemáticas e algoritmos exatos são aqui propostos para alguns desses problemas, em alguns casos pela primeira vez na literatura. Resultados computacionais comprovam que as formulações propostas são fortes e isto se reflete no bom desempenho dos algoritmos utilizados para resolvê-las.
Consider a digraph with costs associated with its arcs and subject to operations of addition, complement or reversal of arcs. When applied, these operations must be of a single, predefined type, aimed at obtaining a digraph that satisfies certain connectivity requirements. Moreover, the total cost of the operations must be minimum. Problems such as these are mostly NP-hard and are commonly associated with the design of particular telecommunication or transport networks. Quite frequently, the connectivity level imposed on the digraphs is reflected by the reseliency, flexibility or operation efficiency required by the underlying networks. Mathematical formulations and exact algorithms are proposed here for some of these problems, in some cases for the very first time in the literature. Computational results indicate that the proposed formulations are strong, as reflected by the good performance of their accompanying algorithms.