History

Please fill in your query. A complete syntax description you will find on the General Help page.
Approximating edge dominating set in dense graphs. (English)
Ogihara, Mitsunori (ed.) et al., Theory and applications of models of computation. 8th annual conference, TAMC 2011, Tokyo, Japan, May 23‒25, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20876-8/pbk). Lecture Notes in Computer Science 6648, 37-47 (2011).
Summary: We study the approximation complexity of the Minimum Edge Dominating Set problem in everywhere $ϵ$-dense and average [‘$(e)$]-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 $\overlineϵ$-dense graphs by using the techniques of Karpinski and Zelikovsky, the approximation ratios of min $\{2,3/(1 + 2ϵ)\}$ and of $\min\{2,3/(3-2\sqrt{1-\overlineϵ})\}$, respectively. On the other hand, we show that it is UGC-hard to approximate the Minimum Edge Dominating Set problem in everywhere $ϵ$-dense graphs with a ratio better than $2/(1 + ϵ)$ with $ϵ> 1/3$ and $2/(2-\sqrt{1-\overlineϵ})$ with $\overlineϵ> 5/9$ in average [‘$(e)$]-dense graphs.