PTAS for the minimum weighted dominating set in growth bounded graphs

Zhong Wang (), Wei Wang (), Joon-Mo Kim (), Bhavani Thuraisingham () and Weili Wu ()

Journal of Global Optimization, 2012, vol. 54, issue 3, 648 pages

Abstract: The minimum weighted dominating set (MWDS) problem is one of the classic NP-hard optimization problems in graph theory with applications in many fields such as wireless communication networks. MWDS in general graphs has been showed not to have polynomial-time constant-approximation if $${\mathcal{NP} \neq \mathcal{P}}$$ . Recently, several polynomial-time constant-approximation SCHEMES have been designed for MWDS in unit disk graphs. In this paper, using the local neighborhood-based scheme technique, we present a PTAS for MWDS in polynomial growth bounded graphs with bounded degree constraint. Copyright Springer Science+Business Media, LLC. 2012

Keywords: Approximation algorithm; Graph theory; PTAS; Dominating set (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-011-9795-x (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:54:y:2012:i:3:p:641-648

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-011-9795-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().