| In this dissertation we consider combinatorial optimization problems. In particular, we concentrate on algorithms that find subgraphs of a given graph of minimum weight that have a certain specified structure.; First, we consider the problem of finding a minimum weight 2-edge-connected spanning subgraph of a given 2-edge-connected graph. For this problem we provide a linear-time exact algorithm for weighted graphs of bounded treewidth, a linear-time PTAS for unweighted planar graphs, and a PTAS for weighted planar graphs.; Furthermore, we design algorithms for the b-edge dominating set problem. We improve upon an existing 8/3-approximation for general weighted graphs, prove limitations of previously used methods, and give linear-time algorithms for this problem on trees. |
