{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:29Z","timestamp":1740144509776,"version":"3.37.3"},"reference-count":13,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T00:00:00Z","timestamp":1614643200000},"content-version":"vor","delay-in-days":60,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["P1-0297","J1-1693","J1-9109"],"award-info":[{"award-number":["P1-0297","J1-1693","J1-9109"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Key R&D Program of China","award":["2019YFA0706402"],"award-info":[{"award-number":["2019YFA0706402"]}]},{"DOI":"10.13039\/501100003453","name":"Natural Science Foundation of Guangdong Province","doi-asserted-by":"publisher","award":["2018A0303130115"],"award-info":[{"award-number":["2018A0303130115"]}],"id":[{"id":"10.13039\/501100003453","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61672051","61309015","61702075"],"award-info":[{"award-number":["61672051","61309015","61702075"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2020,4,28]]},"published-print":{"date-parts":[[2021]]},"abstract":"<jats:p>In a typical wireless telecommunication network, a large number of communication links is established with a limited number of available frequencies. The problem that addresses assigning available frequencies to transmitters such that interference is avoided as far as possible is called the frequency assignment problem. The problem is usually modeled as a graph coloring (labeling) problem. We study in this paper the (<jats:italic>s<\/jats:italic>, <jats:italic>t<\/jats:italic>)-relaxed <jats:italic>L<\/jats:italic>(2, 1)-labeling of a graph which considers the situation where transceivers that are very close receive frequencies that differ by at least two while transceivers that are close receive frequencies that differ by at least one. In addition, the model allows at most <jats:italic>s<\/jats:italic> (resp. <jats:italic>t<\/jats:italic>) anomalies at distance one (resp. two). The objective of the model is to minimize the span of frequencies in a corresponding network. We show that it is NP-complete to decide whether the minimal span of a (1, 0)-relaxed <jats:italic>L<\/jats:italic>(2, 1)-labeling of a graph is at most <jats:italic>k<\/jats:italic>. We also prove that the minimal span of this labeling for two classes of graphs is bounded above with the the square of the largest degree in the graph of interest. These results confirm Conjecture 6 and partially confirm Conjecture 3 stated in Lin [<jats:italic>J. Comb. Optim.<\/jats:italic> <jats:bold>31<\/jats:bold> (2016) 1\u201322].<\/jats:p>","DOI":"10.1051\/ro\/2020043","type":"journal-article","created":{"date-parts":[[2020,4,30]],"date-time":"2020-04-30T08:24:49Z","timestamp":1588235089000},"page":"S1355-S1367","source":"Crossref","is-referenced-by-count":0,"special_numbering":"Supplement","title":["Optimizing distance constraints frequency assignment with relaxation"],"prefix":"10.1051","volume":"55","author":[{"given":"Zehui","family":"Shao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enqiang","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jin","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksander","family":"Vesel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiujun","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2021,3,2]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1016\/j.ipl.2013.06.012","volume":"113","author":"Dai","year":"2013","journal-title":"Inf. Process. Lett"},{"key":"R2","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1007\/s10878-013-9615-y","volume":"29","author":"Dai","year":"2015","journal-title":"J. Comb. Optim"},{"key":"R3","first-page":"319","volume":"130","author":"Dai","year":"2017","journal-title":"ARS Comb"},{"key":"R4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0166-218X(00)00387-5","volume":"113","author":"Fiala","year":"2001","journal-title":"Disc. Appl. Math"},{"key":"R5","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1137\/0405048","volume":"5","author":"Griggs","year":"1992","journal-title":"SIAM J. Disc. Math"},{"key":"R6","doi-asserted-by":"crossref","first-page":"3107","DOI":"10.1016\/j.disc.2012.06.024","volume":"312","author":"Henning","year":"2012","journal-title":"Disc. Math"},{"key":"R7","unstructured":"Kratochv\u00edl J., Kratsch D. and Liedloff M., Exact algorithms for L(2, 1)-labeling of graphs. In Vol. 4708 of Lecture Notes in Computer Science, Springer, Berlin-Heidelberg (2007) 513\u2013524."},{"key":"R8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10878-013-9600-5","volume":"31","author":"Lin","year":"2014","journal-title":"J. Comb. Optim"},{"key":"R9","doi-asserted-by":"crossref","first-page":"1522","DOI":"10.1016\/j.dam.2005.12.006","volume":"154","author":"Schwarz","year":"2006","journal-title":"Disc. Appl. Math"},{"key":"R10","doi-asserted-by":"crossref","first-page":"1188","DOI":"10.1016\/j.aml.2007.12.020","volume":"21","author":"Shao","year":"2008","journal-title":"Appl. Math. Lett"},{"key":"R11","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1007\/s10100-016-0462-7","volume":"25","author":"Shao","year":"2017","journal-title":"Cent. Eur. J. Oper. Res"},{"key":"R12","first-page":"171","volume":"41","author":"Sylvester","year":"1884","journal-title":"Edu. Times"},{"key":"R13","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/s10878-016-9996-9","volume":"34","author":"Zhao","year":"2017","journal-title":"J. Comb. Optim"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2020043\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T09:50:34Z","timestamp":1614678634000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2020043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":13,"alternative-id":["ro180080"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2020043","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2021]]}}}