Adição, complemento e reversão de arcos para satisfazer demandas de conectividade em digrafo

Abstract

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