{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:09:22Z","timestamp":1761894562255},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,6,21]],"date-time":"2007-06-21T00:00:00Z","timestamp":1182384000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2007,7,13]]},"DOI":"10.1007\/s10601-007-9023-y","type":"journal-article","created":{"date-parts":[[2007,6,20]],"date-time":"2007-06-20T18:52:41Z","timestamp":1182365561000},"page":"371-403","source":"Crossref","is-referenced-by-count":22,"title":["Stochastic Local Search Algorithms for Graph Set T-colouring and Frequency Assignment"],"prefix":"10.1007","volume":"12","author":[{"given":"Marco","family":"Chiarandini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"St\u00fctzle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,6,21]]},"reference":[{"issue":"4","key":"9023_CR1","first-page":"261","volume":"1","author":"K. I. Aardal","year":"2003","unstructured":"Aardal, K. I., van Hoesel, C. P. M., Koster, A. M. C. A., Mannino, C., & Sassano, A. (2003). Models and solution techniques for the frequency assignment problem. 4OR: Operational Research Quarterly, 1(4), 261\u2013317 (An updated version to appear in Annals of Operations Research is available at http:\/\/fap.zib.de\/download\/fap2007.ps.gz ).","journal-title":"4OR: Operational Research Quarterly"},{"key":"9023_CR2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0012-365X(99)90037-7","volume":"197-198","author":"S. M. Allen","year":"1999","unstructured":"Allen, S. M., Smith, D. H., & Hurley, S. (1999). Lower bounding techniques for frequency assignment. Discrete Mathematics, 197-198, 41\u201352.","journal-title":"Discrete Mathematics"},{"key":"9023_CR3","doi-asserted-by":"crossref","first-page":"1294","DOI":"10.1109\/TCOM.1973.1091583","volume":"21","author":"L. G. Anderson","year":"1973","unstructured":"Anderson, L. G. (1973). A simulation study of some dynamic channel assignment algorithms in a high capacity mobile telecommunications system. IEEE Transactions on Communications, 21, 1294\u20131301.","journal-title":"IEEE Transactions on Communications"},{"key":"9023_CR4","first-page":"1111","volume-title":"Congress on evolutionary computation (CEC\u201904)","author":"T. Bartz-Beielstein","year":"2004","unstructured":"Bartz-Beielstein, T., & Markon, S. (2004). Tuning search algorithms for real-world applications: A regression tree based approach. In Congress on evolutionary computation (CEC\u201904) (pp. 1111\u20131118). Piscataway NJ: IEEE Press."},{"key":"9023_CR5","first-page":"11","volume-title":"Proceedings of the genetic and evolutionary computation conference (GECCO-2002)","author":"M. Birattari","year":"2002","unstructured":"Birattari, M., St\u00fctzle, T., Paquete, L., & Varrentrapp, K. (2002). A racing algorithm for configuring metaheuristics. In W. B. Langdon, et al. eds., Proceedings of the genetic and evolutionary computation conference (GECCO-2002) (pp. 11\u201318). San Francisco, CA: Morgan Kaufmann."},{"key":"9023_CR6","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1023\/A:1018908907763","volume":"76","author":"R. Bornd\u00f6rfer","year":"1998","unstructured":"Bornd\u00f6rfer, R., Eisenbl\u00e4tter, A., Gr\u00f6tschel, M., & Martin, A. (1998). Frequency assignment in cellular phone networks. Annals of Operation Research, 76, 73\u201393.","journal-title":"Annals of Operation Research"},{"key":"9023_CR7","volume-title":"Classification and regression trees","author":"L. Breiman","year":"1984","unstructured":"Breiman, L., Friedman, J., Olshen, R. A., & Stone, C. J. (1984). Classification and regression trees. Belmont, CA: Wadsworth."},{"issue":"2","key":"9023_CR8","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/BF02125459","volume":"63","author":"D. J. Castelino","year":"1996","unstructured":"Castelino, D. J., Hurley, S., & Stephens, N. M. (1996). A tabu search algorithm for frequency assignment. Annals of Operation Research, 63(2), 301\u2013320.","journal-title":"Annals of Operation Research"},{"key":"9023_CR9","unstructured":"Chiarandini, M. (2005). Stochastic Local Search Methods for Highly Constrained Combinatorial Optimisation Problems. Ph.D. thesis, Computer Science Department, Darmstadt University of Technology, Darmstadt, Germany."},{"key":"9023_CR10","first-page":"162","volume-title":"Third international workshop on hybrid metaheuristics. Lecture Notes in Computer Science Vol.\u00a04030","author":"M. Chiarandini","year":"2006","unstructured":"Chiarandini, M., St\u00fctzle, T., & Larsen, K. S. (2006). Colour reassignment in tabu search for the graph set T-colouring problem. In F. Almeida, J. Marcos Moreno, & M. P\u00e9rez (Eds.), Third international workshop on hybrid metaheuristics. Lecture Notes in Computer Science (Vol.\u00a04030, pp.\u00a0162\u2013177). Berlin: Springer."},{"key":"9023_CR11","volume-title":"Practical nonparametric statistics","author":"W. J. Conover","year":"1999","unstructured":"Conover, W. J. (1999). Practical nonparametric statistics, (3rd ed.). New York: Wiley.","edition":"3"},{"issue":"4","key":"9023_CR12","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02023000","volume":"41","author":"D. Costa","year":"1993","unstructured":"Costa, D. (1993). On the use of some known methods for T-colorings of graphs. Annals of Operation Research, 41(4), 343\u2013358.","journal-title":"Annals of Operation Research"},{"key":"9023_CR13","first-page":"191","volume":"35","author":"M. B. Cozzens","year":"1982","unstructured":"Cozzens, M. B., & Roberts, F. S. (1982). T-colorings of graphs and the channel assignment problem. Congressus Numerantium, 35, 191\u2013208.","journal-title":"Congressus Numerantium"},{"key":"9023_CR14","unstructured":"Culberson, J. C. (1992). Iterated greedy graph coloring and the difficulty landscape. Technical Report 92-07, Department of Computing Science, The University of Alberta, Edmonton, Canada."},{"key":"9023_CR15","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1007\/BFb0017456","volume-title":"Principles and practice of constraint programming - CP97. Lecture notes in computer science Vol.\u00a01330","author":"S. Givry de","year":"1997","unstructured":"de Givry, S., Verfaillie, G., & Schiex, T. (1997). Bounding the optimum of constraint optimization problems. In Principles and practice of constraint programming - CP97. Lecture notes in computer science (Vol.\u00a01330, pp.\u00a0405\u2013419). Berlin: Springer."},{"key":"9023_CR16","first-page":"77","volume-title":"Meta-heuristics: Advances and trends in local search paradigms for optimization","author":"R. Dorne","year":"1998","unstructured":"Dorne, R., & Hao, J. K. (1998). Tabu search for graph coloring, T-colorings and set T-colorings. In Meta-heuristics: Advances and trends in local search paradigms for optimization (pp. 77\u201392). Norwell, MA: Kluwer."},{"key":"9023_CR17","doi-asserted-by":"crossref","first-page":"51","DOI":"10.7151\/dmgt.1158","volume":"22","author":"A. Eisenbl\u00e4tter","year":"2002","unstructured":"Eisenbl\u00e4tter, A., Gr\u00f6tschel, M., & Koster, A. M. C. A. (2002). Frequency assignment and ramifications of coloring. Discussiones Mathematicae Graph Theory, 22, 51\u201388.","journal-title":"Discussiones Mathematicae Graph Theory"},{"issue":"4","key":"9023_CR18","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1023\/A:1009823419804","volume":"3","author":"P. Galinier","year":"1999","unstructured":"Galinier, P., & Hao, J. (1999). Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 3(4), 379\u2013397.","journal-title":"Journal of Combinatorial Optimization"},{"key":"9023_CR19","volume-title":"Computers and Intractability: A Guide to the Theory of $\\cal NP$ -Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of $\\cal NP$ -Completeness. San Francisco, CA: Freeman."},{"issue":"2-3","key":"9023_CR20","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/S0166-218X(02)00576-0","volume":"129","author":"K. Giaro","year":"2003","unstructured":"Giaro, K., Janczewski, R., & Malafiejski, M. (2003). The complexity of the T-coloring problem for graphs with small degree. Discrete Applied Mathematics, 129(2-3), 361\u2013369.","journal-title":"Discrete Applied Mathematics"},{"issue":"2-3","key":"9023_CR21","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0166-218X(02)00575-9","volume":"129","author":"K. Giaro","year":"2003","unstructured":"Giaro, K., Janczewski, R., & Malafiejski, M. (2003). A polynomial algorithm for finding T-span of generalized cacti. Discrete Applied Mathematics, 129(2-3), 371\u2013382.","journal-title":"Discrete Applied Mathematics"},{"issue":"12","key":"9023_CR22","first-page":"1497","volume":"68","author":"W. K. Hale","year":"1980","unstructured":"Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings I.E.E.E., 68(12), 1497\u20131514.","journal-title":"Proceedings I.E.E.E."},{"issue":"1","key":"9023_CR23","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1023\/A:1009690321348","volume":"4","author":"J.-K. Hao","year":"1998","unstructured":"Hao, J.-K., Dorne, R., & Galinier, P. (1998). Tabu search for frequency assignment in mobile radio networks. Journal of Heuristics, 4(1), 47\u201362.","journal-title":"Journal of Heuristics"},{"key":"9023_CR24","unstructured":"Hao, J.-K., & Perrier, L. (1999). Tabu search for the frequency assignment problem in cellular radio networks. Technical Report LGI2P, EMA-EERIE, Parc Scientifique Georges Besse, Nimes, France."},{"key":"9023_CR25","volume-title":"Stochastic local search: Foundations and applications","author":"H. H. Hoos","year":"2004","unstructured":"Hoos, H. H., & St\u00fctzle, T. (2004). Stochastic local search: Foundations and applications. San Francisco, CA: Morgan Kaufmann."},{"issue":"5","key":"9023_CR26","doi-asserted-by":"crossref","first-page":"1921","DOI":"10.1029\/97RS01866","volume":"32","author":"S. Hurley","year":"1997","unstructured":"Hurley, S., Smith, D. H., & Thiel, S. U. (1997). FASoft: A system for discrete channel frequency assignment. Radio Science, 32(5), 1921\u20131939.","journal-title":"Radio Science"},{"key":"9023_CR27","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1016\/S0304-3975(00)00388-1","volume":"262","author":"J. Janssen","year":"2001","unstructured":"Janssen, J., & Narayanan, L. (2001). Approximation algorithms for the channel assignment problem. Theoretical Computer Science, 262, 649\u2013667.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"9023_CR28","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1137\/S0895480101384402","volume":"18","author":"J. Janssen","year":"2005","unstructured":"Janssen, J., Wentzell, T., & Fitzpatrick, S. (2005). Lower bounds from tile covers for the channel assignment problem. SIAM Journal of Discrete Mathematics, 18(4), 679\u2013696.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"9023_CR29","unstructured":"Johnson, D. S., Mehrotra, A., & Trick, M. (Eds.) (2002). Proceedings of the Computational Symposium on Graph Coloring and Its Generalizations, Ithaca, NY."},{"key":"9023_CR30","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1613\/jair.561","volume":"10","author":"D. E. Joslin","year":"1999","unstructured":"Joslin, D. E., & Clements, D. P. (1999). Squeaky wheel optimization. Journal of Artificial Intelligence Research, 10, 353\u2013373.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9023_CR31","unstructured":"Lim, A., Zhang, X., & Zhu, Y. (2003). A hybrid method for the graph coloring and related problems. In Proceedings of MIC\u20192003\u2014The fifth metaheuristics international conference, Kyoto-Japan."},{"key":"9023_CR32","doi-asserted-by":"crossref","first-page":"933","DOI":"10.1145\/1066677.1066892","volume-title":"SAC \u201905: Proceedings of the 2005 ACM symposium on applied computing","author":"A. Lim","year":"2005","unstructured":"Lim, A., Zhu, Y., Lou, Q., & Rodrigues, B. (2005). Heuristic methods for graph coloring problems. In SAC \u201905: Proceedings of the 2005 ACM symposium on applied computing (pp.\u00a0933\u2013939). New York: ACM."},{"key":"9023_CR33","doi-asserted-by":"crossref","unstructured":"Malaguti, E., & Toth, P. (2007). An evolutionary approach for bandwidth multicoloring problems. European Journal of Operational Research, in press (doi: 10.1016\/j.ejor.2006.09.095 ).","DOI":"10.1016\/j.ejor.2006.09.095"},{"key":"9023_CR34","first-page":"1359","volume-title":"Proceedings of the genetic and evolutionary computation conference (GECCO-2001)","author":"S. Matsui","year":"2001","unstructured":"Matsui, S., & Tokoro, K. (2001). Improving the performance of a genetic algorithm for the minimum span frequency assignment problem with an adaptive mutation rate and a new initialization method. In Proceedings of the genetic and evolutionary computation conference (GECCO-2001) (pp. 1359\u20131366). San Francisco, CA: Morgan Kaufmann."},{"key":"9023_CR35","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/3-540-36383-1_5","volume-title":"Experimental algorithmics: From algorithm design to robust and efficient software. Lecture notes in computer science Vol.\u00a02547","author":"C. McGeoch","year":"2002","unstructured":"McGeoch, C., Sanders, P., Fleischer, R., Cohen, P. R., & Precup D. (2002). Using finite experiments to study asymptotic performance. In R. Fleischer, B. Moret, & E. Meineche Schmidt (Eds.) Experimental algorithmics: From algorithm design to robust and efficient software. Lecture notes in computer science (Vol.\u00a02547, pp.\u00a093\u2013126). Berlin: Springer."},{"issue":"1-3","key":"9023_CR36","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0004-3702(92)90007-K","volume":"58","author":"S. Minton","year":"1992","unstructured":"Minton, S., Johnston, M. D., Philips, A. B., & Laird, P. (1992). Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 58(1-3), 161\u2013205.","journal-title":"Artificial Intelligence"},{"key":"9023_CR37","unstructured":"Montemanni, R. (2001). Upper and lower bounds for the fixed spectrum frequency assignment problem. Ph.D. thesis, Division of Mathematics and Statistics, School of Technology, University of Glamorgan, UK."},{"key":"9023_CR38","volume-title":"Design and analysis of experiments","author":"D. C. Montgomery","year":"2005","unstructured":"Montgomery, D. C. (2005). Design and analysis of experiments (6th ed.). New York: Wiley.","edition":"6"},{"key":"9023_CR39","unstructured":"Phan, V., & Skiena, S. (2002). Coloring graphs with a general heuristic search engine. In Johnson et al. [29] (pp. 92\u201399)."},{"issue":"4","key":"9023_CR40","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1023\/A:1014496509129","volume":"34","author":"S. Prestwich","year":"2002","unstructured":"Prestwich, S. (2002). Coloration neighbourhood search with forward checking. Annals of Mathematics and Artificial Intelligence, 34(4), 327\u2013340.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"9023_CR41","unstructured":"Prestwich, S. (2002). Constrained bandwidth multicoloration neighbourhoods. In Johnson et al. [29], (pp. 126\u2013133)."},{"key":"9023_CR42","unstructured":"Prestwich, S. (2003). Hybrid local search on two multicolouring models. In International Symposium on Mathematical Programming, Copenhagen, Denmark."},{"key":"9023_CR43","first-page":"273","volume-title":"CPAIOR, Lecture notes in computer science Vol.\u00a03524","author":"S. Prestwich","year":"2005","unstructured":"Prestwich, S., & Roli, A. (2005). Symmetry breaking and local search spaces. In R. Bart\u00e1k & M. Milano (Eds.), CPAIOR, Lecture notes in computer science (Vol.\u00a03524, pp. 273\u2013287). Berlin Heidelberg New York: Springer."},{"issue":"2-3","key":"9023_CR44","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0012-365X(91)90258-4","volume":"93","author":"F. S. Roberts","year":"1991","unstructured":"Roberts, F. S. (1991). T-colorings of graphs: Recent results and open problems. Discrete Mathematics, 93(2-3), 229\u2013245.","journal-title":"Discrete Mathematics"},{"key":"9023_CR45","first-page":"405","volume-title":"Fundamentals of computation theory. Lecture notes in computer science, Vol.\u00a0380","author":"H. U. Simon","year":"1989","unstructured":"Simon, H. U. (1989). Approximation algorithms for channel assignment in cellular radio networks. In Fundamentals of computation theory. Lecture notes in computer science, (Vol.\u00a0380, pp. 405\u2013415). Berlin: Springer."},{"key":"9023_CR46","doi-asserted-by":"crossref","unstructured":"Sivarajan, K. N., McEliece, R. J., & Ketchum, J. W. (1989). Channel assignment in cellular radio. In Proceedings of the 39th IEEE vehicular technology conference (pp. 846\u2013850).","DOI":"10.1109\/VETEC.1989.40173"},{"issue":"4","key":"9023_CR47","doi-asserted-by":"crossref","first-page":"1265","DOI":"10.1109\/25.875238","volume":"49","author":"D. H. Smith","year":"2000","unstructured":"Smith, D. H., Hurley, S., & Allen, S. M. (2000). A new lower bound for the channel assignment problem. IEEE Transactions on Vehicular Technology, 49(4), 1265\u20131272.","journal-title":"IEEE Transactions on Vehicular Technology"},{"key":"9023_CR48","unstructured":"St\u00fctzle, T. (1998). Local Search Algorithms for Combinatorial Problems\u2014Analysis, Improvements, and New Applications. Ph.D. thesis, FB Informatik, Technische Universit\u00e4t Darmstadt, Darmstadt, Germany."},{"key":"9023_CR49","first-page":"229","volume":"77","author":"B. A. Tesman","year":"1990","unstructured":"Tesman, B. A. (1990). Set T-colorings. Congressus Numerantium, 77, 229\u2013242.","journal-title":"Congressus Numerantium"},{"key":"9023_CR50","unstructured":"Tsang, E., & Voudouris, C. (1998). Solving the radio link frequency assignment problem using guided local search. In NATO Symposium on Radio Length Frequency Assignment, Aalborg, Denmark."},{"key":"9023_CR51","unstructured":"Voudouris, C. (1997). Guided Local Search for Combinatorial Optimization Problems. Ph.D. thesis, University of Essex, Department of Computer Science, Colchester, UK."},{"key":"9023_CR52","unstructured":"Walser, J. P. (1996). Feasible cellular frequency assignment using constraint programming abstractions. In Proceedings of the workshop on constraint programming applications, held in conjunction with CP96, Cambridge, MA."}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-007-9023-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-007-9023-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-007-9023-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T19:14:13Z","timestamp":1559243653000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-007-9023-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,21]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,7,13]]}},"alternative-id":["9023"],"URL":"https:\/\/doi.org\/10.1007\/s10601-007-9023-y","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6,21]]}}}