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

      0 references
      0 references
      0 references
      0 references
      0 references
      2 June 2006
      0 references
      dominating set
      0 references
      complexity
      0 references
      approximation
      0 references
      non-approximability
      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

      Identifiers