Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, September 01, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Dominik Scheder (Univ. of Colorado at Boulder)
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. We analyze several approaches to the general k-ECSS problem of mixed graphs.
For the special case in which undirected edges have no higher weights than directed edges, we achieve a factor 3.75 approximation.
Further, we give several examples on which the analyzed algorithms perform poorly.
Automatic MiSe System Software Version 1.4803M | admin login