Fault-tolerant networks: fast and effective solutions in centralized and distributed settings

Nowadays there is an increasing demand for an efficient and resilient information exchange in communication networks. This means to design, on the one hand, a logical structure onto a given communication infrastructure, which optimizes some sought routing protocol in the absence of failures. On the other hand, to make such a structure resistant against possible link/node malfunctioning, by either adding to it a set of redundant links, which will enter into operation as soon as a failure takes place, or by modifying the existing protocols in order to be able to deal with any malfunctions. Therefore, in the recent past, a lot of work has been done towards the designing of network structures and protocols as reliable as possible. Many different approaches and solutions has been devised, in a broad assortment of settings. The aim of this thesis is to tackle a couple of this settings and solve some new problems and improve some existing results. More in detail we focus on a particular class of problems arising in the centralized setting, namely, the all-best-swap-edge problems. In this case, we want to be able to find a substitute for any link in a tree-based network, that will enter into operation after any malfunction of the original link. Furthermore, we show a result on a problem that belong to the converse setting, the distributed one. In particular, we propose an approximate faulttolerant path-reporting labeling scheme, based on the so-called 2-Hop Cover strategy. In this case, we want to be able to efficiently find a path within a network, even in the presence of a certain set of malfunctions, without using a centralized computation.