Algorithms for Network Design

Abstract

The increasing demand for storing enormous amounts of data while accessing it quickly caused the development of datacenters with flexible connections, so called demand-aware networks. In order to facilitate such networks optimally research is conducted to find algorithms embedding a network in another, sparser, network, or to conclude certain algorithms cannot exist. This thesis is investigating the growth of distances between neighboring nodes when embedding networks: we take a network G and state certain requirements to a host network G∗, to store all information of G while changing the connections. When rearranging the connections we want to minimize the distances created between network nodes that were formerly connected. In the presented work we first show this for transitions between the graph families cycles, paths, and trees, leading up to finding a network with degree ∆ that cannot be embedded in any tree without increasing the distances of at least some neighbors to an order of magnitude of ∆. The results provide on the one hand some basic methods, lower and upper bounds useful for researching transitions not investigated here, on the other hand we found a lower bound of Omega(∆) for the created local distances when hosting general graphs with n nodes in trees and an outline for improving this result to Omega(log n).