{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T14:22:31Z","timestamp":1772893351256,"version":"3.50.1"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>Wireless networks are created by the communication links between a collection of radio transceivers. The nature of wireless transmissions does not lead to arbitrary undirected graphs but to structured graphs which we characterize by the polynomially bounded growth property. In contrast to many existing graph models for wireless networks, the property of polynomially bounded growth is defined independently of geometric data such as positional information.<\/jats:p>\n          <jats:p>On such wireless networks, we present an approach that can be used to create polynomial-time approximation schemes for several optimization problems called the local neighborhood-based scheme. We apply this approach to the problems of seeking maximum (weight) independent sets and minimum dominating sets. These are two important problems in the area of wireless communication networks and are also used in many applications ranging from clustering to routing strategies. However, the approach is presented in a general fashion since it can be applied to other problems as well.<\/jats:p>\n          <jats:p>The approach for the approximation schemes is robust in the sense that it accepts any undirected graph as input and either outputs a solution of desired quality or correctly asserts that the graph presented as input does not satisfy the structural assumption of a wireless network (an NP-hard problem).<\/jats:p>","DOI":"10.1145\/1383369.1383380","type":"journal-article","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T11:56:36Z","timestamp":1219838196000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Approximation schemes for wireless networks"],"prefix":"10.1145","volume":"4","author":[{"given":"Tim","family":"Nieberg","sequence":"first","affiliation":[{"name":"University of Bonn, Lenn\u00e9str, Bonn"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johann","family":"Hurink","sequence":"additional","affiliation":[{"name":"University of Twente, Enschede"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Walter","family":"Kern","sequence":"additional","affiliation":[{"name":"University of Twente, Enschede"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_3"},{"key":"e_1_2_1_2_1","first-page":"567","article-title":"Plongements Lipschitziens dans","volume":"111","author":"Assouad P.","year":"1983","unstructured":"Assouad , P. 1983 . Plongements Lipschitziens dans Rn. Bull. Soc. Math. France 111 , 4, 567 -- 583 . Assouad, P. 1983. Plongements Lipschitziens dans Rn. Bull. Soc. Math. France 111, 4, 567--583.","journal-title":"Rn. Bull. Soc. Math. France"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00014-X"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00294-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.10097"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402676"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 44th IEEE Symposium on Foundations of Computer Science.","author":"Gupta A.","unstructured":"Gupta , A. , Krauthgamer , R. , and Lee , J . 2003. Bounded geometries, fractals, and low-distortion embeddings . In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science. Gupta, A., Krauthgamer, R., and Lee, J. 2003. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0903"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/647548.728759"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/941079.941089"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/wcm.107"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Intelligent Sensors, Sensor Networks and Information Processing Conference. 367--372","author":"Nieberg T.","unstructured":"Nieberg , T. , and Hurink , J . 2004. Wireless communication graphs . In Proceedings of the Intelligent Sensors, Sensor Networks and Information Processing Conference. 367--372 . Nieberg, T., and Hurink, J. 2004. Wireless communication graphs. In Proceedings of the Intelligent Sensors, Sensor Networks and Information Processing Conference. 367--372."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11671411_23"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30559-0_18"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00048-8"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383380","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1383369.1383380","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:59Z","timestamp":1750255079000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383380"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1383369.1383380"],"URL":"https:\/\/doi.org\/10.1145\/1383369.1383380","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2006-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}