{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:38:36Z","timestamp":1770896316793,"version":"3.50.1"},"reference-count":16,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3119,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2005,1]]},"DOI":"10.1016\/j.dam.2004.01.020","type":"journal-article","created":{"date-parts":[[2004,9,28]],"date-time":"2004-09-28T17:43:05Z","timestamp":1096393385000},"page":"326-331","source":"Crossref","is-referenced-by-count":22,"title":["An exact algorithm for the channel assignment problem"],"prefix":"10.1016","volume":"145","author":[{"given":"Daniel","family":"Kr\u00e1l'","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.dam.2004.01.020_bib1","doi-asserted-by":"crossref","unstructured":"R. Beigel, D. Eppstein, 3-coloring in time O(1.3446n): a no-MIS algorithm, in: Proceedings of the FOCS'95, 1995, pp. 444\u2013453. ECCC TR95-033, ftp:\/\/ftp.eccc.uni-trier.de\/.","DOI":"10.1109\/SFCS.1995.492575"},{"key":"10.1016\/j.dam.2004.01.020_bib2","unstructured":"R. Beigel, D. Eppstein, 3-coloring in time O(1.3289n). ACM Computing Research Repository cs.DS\/0006046, 2000."},{"key":"10.1016\/j.dam.2004.01.020_bib3","series-title":"Applied and Algorithmic Graph Theory","author":"Chartrand","year":"1993"},{"key":"10.1016\/j.dam.2004.01.020_bib4","unstructured":"D. Eppstein, Improved algorithms for 3-coloring, 3-edge-coloring and constraint satisfaction, in: Proceedings of the SODA'01, 2001, pp. 329\u2013337. ACM Computing Research Repository cs.DS\/0009006, 2001."},{"key":"10.1016\/j.dam.2004.01.020_bib5","unstructured":"D. Eppstein, Small maximum independent sets and faster exact graph coloring, in: Proceedings of the WADS'01, Lecture Notes in Computer Science, vol. 2125, Springer, Berlin, 2001, pp. 462\u2013470. ACM Computing Research Repository cs.DS\/0011009, 2001."},{"key":"10.1016\/j.dam.2004.01.020_bib6","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0166-218X(00)00387-5","article-title":"Fixed-parameter complexity of \u03bb-labelings","volume":"113","author":"Fiala","year":"2001","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2004.01.020_bib7","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1137\/0405048","article-title":"Labelling graphs with a condition at distance 3","volume":"5","author":"Griggs","year":"1992","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.dam.2004.01.020_bib8","unstructured":"D. Kr\u00e1l', An Exact Algorithm for the Channel Assignment Problem, Technical Report, KAM-DIMATIA series 2002\u2013569, 2002."},{"issue":"3","key":"10.1016\/j.dam.2004.01.020_bib9","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1137\/S0895480101399449","article-title":"A theorem about channel assignment problem","volume":"16","author":"Kr\u00e1l'","year":"2003","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"10.1016\/j.dam.2004.01.020_bib10","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","article-title":"A note on the complexity of the chromatic number problem","volume":"5","author":"Lawler","year":"1976","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.dam.2004.01.020_bib11","unstructured":"C. McDiarmid, Counting and constraint matrices, manuscript, 1998."},{"key":"10.1016\/j.dam.2004.01.020_bib12","series-title":"Recent Advances in Theoretical and Applied Discrete Mathematics","article-title":"Discrete mathematics and radio channel assignment","author":"McDiarmid","year":"2002"},{"key":"10.1016\/j.dam.2004.01.020_bib13","doi-asserted-by":"crossref","unstructured":"C. McDiarmid, On the span in channel assignment problems: bounds, computing and counting, Discrete Math., to appear.","DOI":"10.1016\/S0012-365X(02)00821-X"},{"key":"10.1016\/j.dam.2004.01.020_bib14","unstructured":"C. McDiarmid, B.A. Reed, Channel assignment on graphs of bounded tree width, Discrete Math., to appear."},{"key":"10.1016\/j.dam.2004.01.020_bib15","doi-asserted-by":"crossref","unstructured":"I. Schiermeyer, Deciding 3-colourability in less than O(1.415n) steps, in: Proc. WG'85, Lecture Notes in Computer Science, vol. 790, Springer, Berlin, 1994, pp. 177\u2013182.","DOI":"10.1007\/3-540-57899-4_51"},{"key":"10.1016\/j.dam.2004.01.020_bib16","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1006\/aama.1999.0660","article-title":"Arrangements, channel assignments and associated polynomials","volume":"23","author":"Welsh","year":"1999","journal-title":"Adv. Appl. Math."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X04002562?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X04002562?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T19:27:42Z","timestamp":1734550062000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X04002562"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["S0166218X04002562"],"URL":"https:\/\/doi.org\/10.1016\/j.dam.2004.01.020","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}