scientific article; zbMATH DE number 2172821

From MaRDI portal
Publication:4680214





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.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4680214)