{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,14]],"date-time":"2024-07-14T11:37:57Z","timestamp":1720957077864},"reference-count":23,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2019,1,21]],"date-time":"2019-01-21T00:00:00Z","timestamp":1548028800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004916","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado do Amazonas","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004916","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Int Trans Operational Res"],"published-print":{"date-parts":[[2021,5]]},"abstract":"Abstract<\/jats:title>One of the most important classes of combinatorial optimization problems is graph coloring, and there are several variations of this general problem involving additional constraints either on vertices or edges. They constitute models for real applications, such as channel assignment in mobile wireless networks. In this work, we consider some coloring problems involving distance constraints as weighted edges, modeling them as distance geometry problems (DGPs). Thus, the vertices of the graph are considered as embedded on the real line and the coloring is treated as an assignment of positive integers to the vertices, while the distances correspond to line segments, where the goal is to find their feasible intersection. We formulate these coloring problem variants and show feasibility conditions for some problems. We also propose implicit enumeration methods for some of the optimization problems based on branch\u2010and\u2010prune algorithms proposed for DGPs in the literature. An empirical analysis was undertaken, considering equality and inequality constraints, and uniform and arbitrary set of distances. As the main contributions, we propose new variations of vertex coloring problems in graphs, involving a new theoretical model in distance geometry (DG) for vertex coloring problems with generalized adjacency constraints, promoting the correlation between graph theory and DG fields. We also give a characterization and formal proof of polynomial cases for special graph classes, since the general main problem is\u00a0NP\u2010complete.<\/jats:p>","DOI":"10.1111\/itor.12626","type":"journal-article","created":{"date-parts":[[2019,1,21]],"date-time":"2019-01-21T12:20:36Z","timestamp":1548073236000},"page":"1213-1241","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On distance graph coloring problems"],"prefix":"10.1111","volume":"28","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-7608-2052","authenticated-orcid":false,"given":"Rosiane","family":"de Freitas","sequence":"first","affiliation":[{"name":"Programa de P\u00f3s\u2010Gradua\u00e7\u00e3o em Inform\u00e1tica Instituto de Computa\u00e7\u00e3o Universidade Federal do Amazonas Av. Rodrigo Ot\u00e1vio 3000 69000\u2010000 Manaus Brazil"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-0517-7895","authenticated-orcid":false,"given":"Bruno","family":"Dias","sequence":"additional","affiliation":[{"name":"Programa de P\u00f3s\u2010Gradua\u00e7\u00e3o em Inform\u00e1tica Instituto de Computa\u00e7\u00e3o Universidade Federal do Amazonas Av. Rodrigo Ot\u00e1vio 3000 69000\u2010000 Manaus Brazil"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-3897-3356","authenticated-orcid":false,"given":"Nelson","family":"Maculan","sequence":"additional","affiliation":[{"name":"Programa de Engenharia de Sistemas e Computa\u00e7\u00e3o COPPE Universidade Federal do Rio de Janeiro C.P. 68530 21945\u2010970 Rio de Janeiro Brazil"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-7538-7305","authenticated-orcid":false,"given":"Jayme","family":"Szwarcfiter","sequence":"additional","affiliation":[{"name":"Programa de Engenharia de Sistemas e Computa\u00e7\u00e3o COPPE Universidade Federal do Rio de Janeiro C.P. 68530 21945\u2010970 Rio de Janeiro Brazil"}]}],"member":"311","published-online":{"date-parts":[[2019,1,21]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/itor.12283"},{"key":"e_1_2_8_3_1","doi-asserted-by":"publisher","DOI":"10.1111\/1475-3995.00349"},{"key":"e_1_2_8_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403039"},{"key":"e_1_2_8_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/wcm.898"},{"key":"e_1_2_8_6_1","doi-asserted-by":"crossref","unstructured":"Bordini A. Protti F. da Silva T. Filho G. 2019.New algorithms for the minimum coloring cut problem.International Transactions in Operational Research26 1868\u20131883.","DOI":"10.1111\/itor.12494"},{"key":"e_1_2_8_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/0470846224"},{"key":"e_1_2_8_8_1","unstructured":"deFreitas R. Dias B. Maculan N. Szwarcfiter J. 2016.Distance geometry approach for special graph coloring problems. Available athttps:\/\/arxiv.org\/abs\/1606.04978(accessed August 15 2018) ."},{"key":"e_1_2_8_9_1","unstructured":"Dias B. 2014.Theoretical models and algorithms for optimizing channel assignment in wireless mobile networks. Master's thesis Federal University of Amazonas Brazil (in Portuguese)."},{"key":"e_1_2_8_10_1","unstructured":"Dias B. deFreitas R. Maculan N. Michelon P. 2016.Solving the bandwidth coloring problem applying constraint and integer programming techniques.Optimization Online. Available athttp:\/\/www.optimization\u2010online.org\/DB_HTML\/2016\/06\/5514.html(accessed August 15 2018)."},{"key":"e_1_2_8_11_1","doi-asserted-by":"publisher","DOI":"10.1111\/itor.12249"},{"key":"e_1_2_8_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1980.11899"},{"key":"e_1_2_8_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_8_14_1","unstructured":"Koster A. 1999.Frequency assignment: models and algorithms. PhD thesis Universiteit Maastricht the Netherlands."},{"key":"e_1_2_8_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02250-0"},{"key":"e_1_2_8_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2012.09.003"},{"key":"e_1_2_8_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-011-9402-6"},{"key":"e_1_2_8_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2011.11.007"},{"key":"e_1_2_8_19_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2007.00622.x"},{"key":"e_1_2_8_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/120875909"},{"key":"e_1_2_8_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2009.00696.x"},{"key":"e_1_2_8_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-011-0358-3"},{"key":"e_1_2_8_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-5128-0"},{"key":"e_1_2_8_24_1","unstructured":"Saxe J. 1979.Embeddability of weighted graphs ink\u2010space is strongly NP\u2010hard. Proceedings of 17th Allerton Conference in Communications Control and Computing Monticello IL pp.480\u2013489."}],"container-title":["International Transactions in Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1111%2Fitor.12626","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/itor.12626","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1111\/itor.12626","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/itor.12626","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T23:16:03Z","timestamp":1693869363000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1111\/itor.12626"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,21]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["10.1111\/itor.12626"],"URL":"https:\/\/doi.org\/10.1111\/itor.12626","archive":["Portico"],"relation":{},"ISSN":["0969-6016","1475-3995"],"issn-type":[{"value":"0969-6016","type":"print"},{"value":"1475-3995","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,21]]},"assertion":[{"value":"2018-08-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-27","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
