{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T09:36:05Z","timestamp":1725615365963},"reference-count":27,"publisher":"IGI Global","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,10,1]]},"abstract":"<p>The authors present an experimental investigation of tabu search (TS) to solve the 3-coloring problem (3-COL). Computational results reveal that a basic TS algorithm is able to find proper 3-colorings for random 3-colorable graphs with up to 11000 vertices and beyond when instances follow the uniform or equipartite well-known models, and up to 1500 vertices for the hardest class of flat graphs. This study also validates and reinforces some existing phase transition thresholds for 3-COL.<\/p>","DOI":"10.4018\/jamc.2010100101","type":"journal-article","created":{"date-parts":[[2011,10,19]],"date-time":"2011-10-19T15:57:56Z","timestamp":1319039876000},"page":"1-24","source":"Crossref","is-referenced-by-count":5,"title":["A Study of Tabu Search for Coloring Random 3-Colorable Graphs Around the Phase Transition"],"prefix":"10.4018","volume":"1","author":[{"given":"Jean-Philippe","family":"Hamiez","sequence":"first","affiliation":[{"name":"Universit\u00e9 d\u2019Angers\/LERIA, France"}]},{"given":"Jin-Kao","family":"Hao","sequence":"additional","affiliation":[{"name":"Universit\u00e9 d\u2019Angers, France"}]},{"given":"Fred W.","family":"Glover","sequence":"additional","affiliation":[{"name":"OptTek Systems Inc., USA"}]}],"member":"2432","reference":[{"key":"jamc.2010100101-0","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.09.013"},{"key":"jamc.2010100101-1","doi-asserted-by":"crossref","unstructured":"Barbosa, V. C., & Ferreira, R. G. (2004). On the phase transitions of graph coloring and independent sets. Physica A: Statistical Mechanics and its Applications, 343, 401-423.","DOI":"10.1016\/j.physa.2004.05.055"},{"key":"jamc.2010100101-2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.68.036702"},{"key":"jamc.2010100101-3","doi-asserted-by":"publisher","DOI":"10.1145\/359094.359101"},{"key":"jamc.2010100101-4","unstructured":"Cheeseman, P., Kanefsky, B., & Taylor, W. M. (1991). Where the really hard problems are. In J. Mylopoulos & R. Reiter (Eds.), Twelfth International Joint Conference on Artificial Intelligence (Vol. 1, pp. 331-337). San Francisco: Morgan Kaufmann."},{"key":"jamc.2010100101-5","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00164-5"},{"key":"jamc.2010100101-6","first-page":"77","article-title":"Tabu search for graph coloring, T-colorings and set T-colorings","author":"R.Dorne","year":"1998","journal-title":"Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization"},{"issue":"1-2","key":"jamc.2010100101-7","volume":"265","author":"O.Dubois","year":"2001","journal-title":"Theoretical Computer Science"},{"key":"jamc.2010100101-8","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009638304510"},{"key":"jamc.2010100101-9","doi-asserted-by":"crossref","unstructured":"Erben, W. (2001). A grouping genetic algorithm for graph colouring and exam timetabling. In E. Burke & W. Erben (Eds.), Practice and Theory of Automated Timetabling III (LNCS 2079, pp. 132-156). Berlin: Springer.","DOI":"10.1007\/3-540-44629-X_9"},{"key":"jamc.2010100101-10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125407"},{"key":"jamc.2010100101-11","doi-asserted-by":"crossref","unstructured":"Fleurent, C., & Ferland, J. (1996b). Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability. In D. S. Johnson & M. A. Trick (Eds.), Cliques, Coloring, and Satisfiability (Volume 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 619-652). New Providence, NJ: American Mathematical Society.","DOI":"10.1090\/dimacs\/026\/29"},{"key":"jamc.2010100101-12","author":"M. R.Garey","year":"1979","journal-title":"Computers and Intractability: A Guide to the Theory of NP-Completness"},{"key":"jamc.2010100101-13","unstructured":"Gent, I. P., MacIntyre, E., Prosser, P., & Walsh, T. (1996). The constrainedness of search. In W. J. Clancey, D. Weld, H. E. Shrobe, & T. E. Senator (Eds.), Thirteenth National Conference on Artificial Intelligence (Vol. 1, pp. 246-252). Menlo Park, CA: AAAI Press."},{"key":"jamc.2010100101-14","doi-asserted-by":"crossref","unstructured":"Glover, F. W., & Laguna, M. (1997). Tabu Search. Dordrecht, The Netherladns: Kluwer.","DOI":"10.1007\/978-1-4615-6089-0"},{"key":"jamc.2010100101-15","doi-asserted-by":"publisher","DOI":"10.1002\/3527606734"},{"key":"jamc.2010100101-16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02239976"},{"issue":"1-2","key":"jamc.2010100101-17","volume":"81","author":"T.Hogg","year":"1996","journal-title":"Artificial Intelligence"},{"key":"jamc.2010100101-18","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","article-title":"Reducibility among combinatorial problems","author":"R. M.Karp","year":"1972","journal-title":"Complexity of Computer Computations"},{"key":"jamc.2010100101-19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702418759"},{"key":"jamc.2010100101-20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32439-3_10"},{"key":"jamc.2010100101-21","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.046705"},{"key":"jamc.2010100101-22","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)89267-9"},{"key":"jamc.2010100101-23","doi-asserted-by":"publisher","DOI":"10.1038\/22055"},{"key":"jamc.2010100101-24","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90214-8"},{"key":"jamc.2010100101-25","article-title":"Random graphs","volume":"Vol. 78","author":"B.Bollob\u00e1s","year":"2001","journal-title":"Cambridge Studies in Advanced Mathematics"},{"key":"jamc.2010100101-26","doi-asserted-by":"crossref","unstructured":"Zdeborov\u00e1, L., & Krzaka\u0142a, F. (2007). Phase transitions in the coloring of random graphs. Physical Review E.","DOI":"10.1103\/PhysRevE.76.031131"}],"container-title":["International Journal of Applied Metaheuristic Computing"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=51675","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T23:56:36Z","timestamp":1654127796000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jamc.2010100101"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2010,10,1]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,10]]}},"URL":"https:\/\/doi.org\/10.4018\/jamc.2010100101","relation":{},"ISSN":["1947-8283","1947-8291"],"issn-type":[{"value":"1947-8283","type":"print"},{"value":"1947-8291","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,1]]}}}