{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T02:28:22Z","timestamp":1768789702023,"version":"3.49.0"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p> In this paper, we address the problem of gathering information in one node (sink) of a radio network where interference constraints are present: 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 interferences that do 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. We are interested in finding a gathering protocol, that is an ordered sequence of rounds (each round consists of noninterfering simultaneous transmissions) such that w(u) messages are transmitted from any node u to a fixed node called the sink. Our aim is to find a gathering protocol with the minimum number of rounds (called gathering time). In this article, we focus on the specific case where the network is a path with the sink at an end vertex of the path and where the traffic is unitary (w(u) = 1 for all u); indeed this simple case appears to be already very difficult. We first give a new lower bound and a protocol with a gathering time that differ only by a constant independent of the length of the path. Then we present a method to construct incremental protocols. An incremental protocol for the path on n + 1 vertices is obtained from a protocol for n vertices by adding new rounds and new calls to some rounds but without changing the calls of the original rounds. We show that some of these incremental protocols are optimal for many values of d<jats:sub>T<\/jats:sub> and d<jats:sub>I<\/jats:sub> (in particular when d<jats:sub>T<\/jats:sub> is prime). We conjecture that this incremental construction always gives optimal protocols. Finally, we derive an approximation algorithm when the sink is placed in an arbitrary vertex in the path. <\/jats:p>","DOI":"10.1142\/s1793830913500043","type":"journal-article","created":{"date-parts":[[2013,5,3]],"date-time":"2013-05-03T10:01:57Z","timestamp":1367575317000},"page":"1350004","source":"Crossref","is-referenced-by-count":6,"title":["GATHERING RADIO MESSAGES IN THE PATH"],"prefix":"10.1142","volume":"05","author":[{"given":"JEAN-CLAUDE","family":"BERMOND","sequence":"first","affiliation":[{"name":"Mascotte Project, INRIA\u2013I3S(CNRS\/UNSA), Sophia Antipolis, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RALF","family":"KLASING","sequence":"additional","affiliation":[{"name":"CNRS - LaBRI - Universit\u00e9 de Bordeaux, 351 Cours de la Lib\u00e9ration, 33405 Talence Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"NELSON","family":"MORALES","sequence":"additional","affiliation":[{"name":"Delphos Mine Planning Lab, Advanced Mining Technology Center, University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ST\u00c9PHANE","family":"P\u00c9RENNES","sequence":"additional","affiliation":[{"name":"Mascotte Project, INRIA\u2013I3S(CNRS\/UNSA), Sophia Antipolis, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PATRICIO","family":"REYES","sequence":"additional","affiliation":[{"name":"Department of Statistics, Universidad Carlos III de Madrid, 28903 Getafe Madrid, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2013,5,3]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.04.037"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626406002551"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00022-5"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1142\/S0219265910002714"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795283619"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.07.021"},{"key":"rf9","first-page":"109","volume":"9","author":"Bermond J.-C.","journal-title":"Ad Hoc Sensor Wireless Netw."},{"key":"rf10","first-page":"16","volume":"22","author":"Bertin P.","journal-title":"France Telecom R&D"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1109\/49.840210"},{"key":"rf12","doi-asserted-by":"crossref","unstructured":"V.\u00a0Bonifaci, Graphs and Algorithms in Communication Networks, Springer Monograph, eds. A.\u00a0Koster and X.\u00a0Munoz (Springer-Verlag, 2010)\u00a0pp. 357\u2013377.","DOI":"10.1007\/978-3-642-02250-0_14"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.06.001"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1109\/26.79285"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00004-4"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.11.004"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2004.830927"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00292-4"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1007\/11821069_35"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.01.015"},{"key":"rf25","series-title":"Springer Monograph","volume-title":"Dissemination of Information in Communication Networks: Part I. Broadcasting, Gossiping, Leader Election, and Fault-Tolerance","author":"Hromkovi\u010d J.","year":"2005"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(03)00212-3"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.048"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2006.283821"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830913500043","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:16:59Z","timestamp":1565122619000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830913500043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":22,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2013,5,3]]},"published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1142\/S1793830913500043"],"URL":"https:\/\/doi.org\/10.1142\/s1793830913500043","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3]]}}}