Approximation Algorithms for Connected Graph Factor Problems

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.