Algorithms for Network Design
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Master's thesis
Authors
Date
2024-09-30
Department
Major/Subject
Computer Science
Mcode
Degree programme
Master's Programme in Computer, Communication and Information Sciences
Language
en
Pages
39
Series
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).Description
Supervisor
Uitto, JaraKeywords
nNetworks, graphs, distances, theory, computer science, algorithms