{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T00:18:29Z","timestamp":1768781909641,"version":"3.49.0"},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p> In this paper, we address the problem of gathering information in a specific node (or sink) of a radio network, where interference constraints are present. We take into account the fact that, when a node transmits, it produces interference in an area bigger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most d<jats:sub>T<\/jats:sub> in the graph, but when doing so it generates interference that does not allow nodes at distance up to d<jats:sub>I<\/jats:sub> (d<jats:sub>I<\/jats:sub> \u2265 d<jats:sub>T<\/jats:sub>) to listen to other transmissions. Time is synchronous and divided into time-steps in each of which a round (set of non-interfering radio transmissions) is performed. We give general lower bounds on the number of rounds required to gather into a sink of a general graph, and present an algorithm working on any graph, with an approximation factor of 4. We also show that the problem of finding an optimal strategy for gathering is NP-HARD, for any values of d<jats:sub>I<\/jats:sub> and d<jats:sub>T<\/jats:sub>. If d<jats:sub>I<\/jats:sub> &gt; d<jats:sub>T<\/jats:sub>, we show that the problem remains hard when restricted to the uniform case where each vertex in the network has exactly one piece of information to communicate to the sink. <\/jats:p>","DOI":"10.1142\/s0129626406002551","type":"journal-article","created":{"date-parts":[[2006,7,20]],"date-time":"2006-07-20T07:36:02Z","timestamp":1153380962000},"page":"165-183","source":"Crossref","is-referenced-by-count":36,"title":["HARDNESS AND APPROXIMATION OF GATHERING IN STATIC RADIO NETWORKS"],"prefix":"10.1142","volume":"16","author":[{"given":"JEAN-CLAUDE","family":"BERMOND","sequence":"first","affiliation":[{"name":"MASCOTTE project 13S\/CNRS\/Universit\u00e9 de Nice\/Sophia-Antipolis, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JEROME","family":"GALTIER","sequence":"additional","affiliation":[{"name":"France Telecom Research and Development, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RALF","family":"KLASING","sequence":"additional","affiliation":[{"name":"LaBRI - Universit\u00e9 Bordeaux 1 - CNRS, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"NELSON","family":"MORALES","sequence":"additional","affiliation":[{"name":"MASCOTTE project 13S\/CNRS\/Universit\u00e9 de Nice\/Sophia-Antipolis, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"STEPHANE","family":"PERENNES","sequence":"additional","affiliation":[{"name":"MASCOTTE project 13S\/CNRS\/Universit\u00e9 de Nice\/Sophia-Antipolis, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00022-5"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795283619"},{"key":"rf8","first-page":"16","volume":"22","author":"Bertin P.","journal-title":"France Telecom R&D"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1109\/49.840210"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1109\/26.79285"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00004-4"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.11.004"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00292-4"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"rf20","series-title":"Springer Monograph","volume-title":"Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance","author":"Hromkovic J.","year":"2005"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626406002551","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:15:28Z","timestamp":1565093728000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626406002551"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":11,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1142\/S0129626406002551"],"URL":"https:\/\/doi.org\/10.1142\/s0129626406002551","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}