
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 2010  Copyright 2010 Universität Bonn, Institut für Informatik, Abt. V  
85311 18.02.2010 
On Approximation Complexity of Edge Dominating Set Problem in Dense Graphs
Richard Schmied and Claus Viehmann [Download PostScript] [Download PDF]
We study the approximation complexity of the Minimum Edge Dominating Set problem
in everywhere εdense and average εdense graphs.
More precisely, we consider the computational complexity of approximating a generalization
of the Minimum Edge Dominating Set problem, the so called Minimum Subset Edge Dominating Set problem.
As a direct result, we obtain for the special case of the Minimum Edge Dominating Set problem in
everywhere εdense and average εdense graphs
by using the techniques of Karpinski and Zelikovsky, the approximation ratios of min{2,3/(1+2ε)} and of
min{2,3/(32\sqrt{1ε})}, respectively. 

Last Change:
11/05/14 at 10:54:19
English 
Universität Bonn > Institut für Informatik > Abteilung V 