The problem of finding the minimum weight k-edge connected spanning subgraph of a mixed graph is NP-hard for every k ≥ 1, and, for k ≥ 2, the best approximation ratio known so far is 4. In this thesis, we analyze several approaches to the general k-ECSS problem of mixed graphs.; We give a factor 2 approximation for a special case in which all undirected edges have the same weight, and this weight is no higher than twice the weight of the cheapest directed edge. For the special case in which undirected edges have no higher weights than directed edges (though not necessarily being uniform) we achieve a factor 3.75 approximation.; Further, we give several examples on which the analyzed algorithms perform poorly.
展开▼
