University of Twente Student Theses

Login
As of Friday, 8 August 2025, the current Student Theses repository is no longer available for thesis uploads. A new Student Theses repository will be available starting Friday, 15 August 2025.

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:https://purl.utwente.nl/essays/66465
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page