University of Twente Student Theses

Login

Approximation Algorithms for Connected Graph Factor Problems

Waanders, M.J.C (2014) Approximation Algorithms for Connected Graph Factor Problems.

[img] PDF
366kB
Abstract:Creating low cost networks that satisfy certain connectivity requirements is one of the main concerns within network design. Examples of this problem include VLSI design, vehicle routing and communication networks. This thesis describes two approximation algorithms for creating a low weight k-edge-connected d-regular subgraph under the assumption that edge weights satisfy the triangle inequality. These algorithms increase the connectivity of a d-regular graph until it is a k-edge-connected graph, without changing the degree of any vertex.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics, 54 computer science
Programme:Applied Mathematics MSc (60348)
Link to this item:http://purl.utwente.nl/essays/66465
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page