No label defined (Q4680214)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2172821
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 2172821 |
Statements
2 June 2006
0 references
dominating set
0 references
complexity
0 references
approximation
0 references
non-approximability
0 references
0.91834295
0 references
0 references
0.90585136
0 references
0.90585136
0 references
0.9003809
0 references
0.9003809
0 references
0.8984461
0 references
0.89554894
0 references
0.8922676
0 references
0.8922676
0 references
For a graph \(G=(E, V)\), \(| V| =n\), and a positive function \(f(n)\) the measured dominating set problem is to find the minimum set of vertices \(D\), s.t. for any vertex \(u\in V- D\) there exists \(v \in D\) with distance \((u,v) \leq f(n)\). If \(f(n)=1\), we get the standard dominating set problem. The Contribution of the paper is the following: A) The problem is NP-hard for \(f(n)=n^{\varepsilon },\, 0<\varepsilon <1\). This extends a former result of \textit{G. J. Chang} and \textit{G. L. Nemhauser} [Oper. Res. Lett. 1, 214--218 (1982; Zbl 0498.90023)] for \(f(n)=O(1)\). B) The problem is approximable with a ratio of \(O(\log n)\) and the log function is the best possible. The same results are proved for the weighted version of the problem.
0 references