1. On Approximating (Connected) 2-Edge Dominating Set by a Tree.
- Author
-
Fujito, Toshihiro and Shimoda, Tomoaki
- Subjects
- *
SET theory , *APPROXIMATION theory , *EDGES (Geometry) , *DOMINATING set , *MATHEMATICAL connectedness - Abstract
The
edge dominating set problem (EDS) is to compute a minimum size edge set such that every edge is dominated by some edge in it. This paper considers a variant of EDS with extensions of multiple and connected dominations combined. In theb -EDS problem, each edge needs to be dominatedb times. Connected EDS requires an edge dominating set to be connected while it has to form a tree in Tree Cover. Although each of EDS,b -EDS, and Connected EDS (or Tree Cover) has been well studied, each known to be approximable within 2 (or 8/3 forb -EDS in general), nothing is known when these extensions are imposed simultaneously on EDS unlike in the case of the (vertex) dominating set problem. We consider Connected 2-EDS and 2-Tree Cover (i.e., a combination of 2-EDS and Tree Cover), and present a polynomial algorithm approximating each within 2. Moreover, it will be shown that the single tree computed is no larger than twice the optimum for (not necessarily connected) 2-EDS, thus also approximating 2-EDS equally well. It also implies that 2-EDS with clustering properties can be approximated within 2 as well. [ABSTRACT FROM AUTHOR]- Published
- 2018
- Full Text
- View/download PDF