University of Twente Student Theses


Approximation Algorithms for Connected Graph Factor Problems

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

[img] PDF
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:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page