{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:18:42Z","timestamp":1775053122734,"version":"3.50.1"},"reference-count":54,"publisher":"IGI Global","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,7,1]]},"abstract":"<p>The graph coloring problem (GCP) is a widely studied combinatorial optimization problem due to its numerous applications in many areas, including time tabling, frequency assignment, and register allocation. The need for more efficient algorithms has led to the development of several GC solvers. In this paper, the authors introduce a team of Finite Learning Automata, combined with the random walk algorithm, using Boolean satisfiability encoding for the GCP. The authors present an experimental analysis of the new algorithm\u2019s performance compared to the random walk technique, using a benchmark set containing SAT-encoding graph coloring test sets.<\/p>","DOI":"10.4018\/jamc.2010070101","type":"journal-article","created":{"date-parts":[[2011,2,15]],"date-time":"2011-02-15T20:23:11Z","timestamp":1297801391000},"page":"1-19","source":"Crossref","is-referenced-by-count":6,"title":["Stochastic Learning for SAT- Encoded Graph Coloring Problems"],"prefix":"10.4018","volume":"1","author":[{"given":"Noureddine","family":"Bouhmala","sequence":"first","affiliation":[{"name":"Vestfold University College, Norway"}]},{"given":"Ole-Christoffer","family":"Granmo","sequence":"additional","affiliation":[{"name":"University of Agder, Norway"}]}],"member":"2432","reference":[{"key":"jamc.2010070101-0","doi-asserted-by":"publisher","DOI":"10.1145\/937503.937505"},{"key":"jamc.2010070101-1","doi-asserted-by":"publisher","DOI":"10.1145\/359094.359101"},{"key":"jamc.2010070101-2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.19.4.456"},{"key":"jamc.2010070101-3","article-title":"Stochastic local search algorithms for the graph colouring problem","author":"M.Chiarandini","year":"2007","journal-title":"Handbook of Approximation Algorithms and Metaheuristics"},{"key":"jamc.2010070101-4","doi-asserted-by":"crossref","unstructured":"Cook, S. A. (1971). The complexity of theorem-proving procedures. In Proceedings of the Third ACM Symposium on Theory of Computing (pp. 151-158).","DOI":"10.1145\/800157.805047"},{"key":"jamc.2010070101-5","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1090\/dimacs\/026\/13","article-title":"Exploring the k-colorable landscape with iterated greedy","author":"J. C.Culberson","year":"1996","journal-title":"Cliques, Coloring, and Satisfiability: 2nd DIMACS Implementation Challenge"},{"key":"jamc.2010070101-6","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2009.00696.x"},{"issue":"7","key":"jamc.2010070101-7","first-page":"1420","article-title":"A minimal state processing search algorithm for graph coloring problems.","volume":"83-A","author":"N.Funabiki","year":"2000","journal-title":"IEICE Transactions Fundamentals E"},{"key":"jamc.2010070101-8","doi-asserted-by":"publisher","DOI":"10.1109\/12.53585"},{"key":"jamc.2010070101-9","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009823419804"},{"key":"jamc.2010070101-10","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.07.028"},{"key":"jamc.2010070101-11","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.07.017"},{"key":"jamc.2010070101-12","first-page":"28","article-title":"Towards an Understanding of Hill-Climbing Procedures for SAT. In","volume":"93","author":"L. P.Gent","year":"1993","journal-title":"Proceedings of AAAI"},{"key":"jamc.2010070101-13","first-page":"73","article-title":"Unsatisfied Variables in Local Search","author":"L. P.Gent","year":"1995","journal-title":"Hybrid Problems, Hybrid Solutions"},{"issue":"3","key":"jamc.2010070101-14","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","article-title":"Tabu Search - Part 1.","volume":"1","author":"F.Glover","year":"1989","journal-title":"ORSA Journal on Computing"},{"issue":"3","key":"jamc.2010070101-15","first-page":"15","article-title":"Solving the Satisfiability Problem Using Finite Learning Automata.","volume":"4","author":"O.-C.Granmo","year":"2007","journal-title":"International Journal of Computer Science and Applications"},{"key":"jamc.2010070101-16","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2009.189"},{"key":"jamc.2010070101-17","doi-asserted-by":"crossref","unstructured":"Granmo, O.-C., Oommen, B. J., Myrer, S. A., & Olsen, M. G. (2007). Learning Automata-Based Solutions to the Nonlinear Fractional Knapsack Problem with Applications to Optimal Resource Allocation. IEEE Transactions on Systems, Man and Cybernetics, SMC-37(B), 166-175.","DOI":"10.1109\/TSMCB.2006.879012"},{"key":"jamc.2010070101-18","unstructured":"Hansen, P., Labbe, M., & Schindl, D. (2005). Set covering and packing formulations of graph coloring: algorithms and first polyhedral results (Tech. Rep. No. G-2005-76). GERARD, Universite de Montreal, Quebec, Canada."},{"key":"jamc.2010070101-19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02239976"},{"key":"jamc.2010070101-20","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.03.022"},{"key":"jamc.2010070101-21","unstructured":"Hoos, H. (2002). An adaptive noise mechanism for Walk-SAT. In Proceedings of the Eighteenth National Conference in Artificial Intelligence (pp. 655-660)."},{"key":"jamc.2010070101-22","doi-asserted-by":"crossref","unstructured":"Hutter, F., Tompkins, D., & Hoos, H. (2002). Scaling and probabilistic smoothing: Efficient dynamic local search for SAT. In Proceedings of the Eight International Conference of the Principles and Practice of Constraint Programming (pp. 233-248).","DOI":"10.1007\/3-540-46135-3_16"},{"key":"jamc.2010070101-23","doi-asserted-by":"crossref","unstructured":"Ishtaiwi, A., Thornton, J., Sattar, A., & Pham, D. N. (2005). Neighborhood clause weight redistribution in local search for SAT. In Proceedings of the Eleventh International Conference on Principles and Practice Programming (LNCS 3709, pp. 772-776).","DOI":"10.1007\/11564751_62"},{"key":"jamc.2010070101-24","doi-asserted-by":"publisher","DOI":"10.1287\/opre.39.3.378"},{"key":"jamc.2010070101-25","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.10.007"},{"key":"jamc.2010070101-26","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","article-title":"Reducibility among combinatorial problems","author":"R.Karp","year":"1972","journal-title":"Complexity of computer computations"},{"key":"jamc.2010070101-27","unstructured":"KhudaBukhsh. A. R., Xu, L., Hoos, H., & Leyton-Brown, K. (2009). SATenstein: Automatically Building Local Search SAT Solvers from Components. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI-09)."},{"issue":"6","key":"jamc.2010070101-28","doi-asserted-by":"crossref","first-page":"489","DOI":"10.6028\/jres.084.024","article-title":"A graph coloring algorithm for large scheduling problems.","volume":"84","author":"F. T.Leighton","year":"1979","journal-title":"Journal of Research of the National Bureau of Standards"},{"key":"jamc.2010070101-29","doi-asserted-by":"crossref","unstructured":"Li, C. M., & Huang, W. Q. (2005). Diversification and determinism in local search for satisfiability. In Proceedings of the Eight International Conference on Theory and Applications of Satisfiability Testing (SAT-05) (LNCS 3569, pp. 158-172).","DOI":"10.1007\/11499107_12"},{"key":"jamc.2010070101-30","unstructured":"Li, C. M., Wei, W., & Zhang, H. (2007). Combining adaptive noise and look-ahead in local search for SAT. In Proceedings of the Tenth International Conference on Theory and Applications of Satisfiability Testing (LNCS 4501)."},{"key":"jamc.2010070101-31","doi-asserted-by":"crossref","unstructured":"Li, C. M., Wei, W., & Zhang, H. (2007). Combining adaptive noise and look-ahead in local search for SAT. In Proceedings of the Tenth International Conference on Theory and Applications of Satisfiability Testing (SAT-07) (LNCS 4501, pp. 121-133).","DOI":"10.1007\/978-3-540-72788-0_15"},{"key":"jamc.2010070101-32","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2009.00696.x"},{"key":"jamc.2010070101-33","first-page":"321","article-title":"Evidence for Invariants in Local Search. In","volume":"97","author":"D.McAllester","year":"1997","journal-title":"Proceedings of AAAI"},{"key":"jamc.2010070101-34","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.07.010"},{"key":"jamc.2010070101-35","author":"K. S.Narendra","year":"1989","journal-title":"Learning Automata: An Introduction"},{"key":"jamc.2010070101-36","doi-asserted-by":"publisher","DOI":"10.1137\/0216047"},{"key":"jamc.2010070101-37","doi-asserted-by":"publisher","DOI":"10.1109\/12.75146"},{"key":"jamc.2010070101-38","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.1045"},{"key":"jamc.2010070101-39","doi-asserted-by":"publisher","DOI":"10.1109\/12.485372"},{"key":"jamc.2010070101-40","first-page":"9","article-title":"Auto-Walk-sat: A Self-Tuning Implementation of Walk-sat.","author":"D. J.Patterson","year":"2001","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"jamc.2010070101-41","doi-asserted-by":"crossref","unstructured":"Prestwich, S. (2004). Local Search on SAT-encoded Colouring Problems. In Theory and Applications of Satisfiability Testing (LNCS 2919, pp. 105-119).","DOI":"10.1007\/978-3-540-24605-3_9"},{"key":"jamc.2010070101-42","doi-asserted-by":"crossref","unstructured":"Prestwich, S. (2005). Random walk with continuously smoothed variable weights. In Proceedings of the Eight International Conference on Theory and Applications of Satisfiability Testing (SAT-05) (LNCS 3569, pp. 203-215).","DOI":"10.1007\/11499107_15"},{"key":"jamc.2010070101-43","first-page":"297","article-title":"Local search characteristics of incomplete SAT procedures. In","volume":"AAAI-2000","author":"D.Schuurmans","year":"2000","journal-title":"Proceedings"},{"key":"jamc.2010070101-44","first-page":"334","article-title":"The exponentiated sub-gradient algorithm for heuristic Boolean programming. In","volume":"IJCAI-01","author":"D.Schuurmans","year":"2001","journal-title":"Proceedings"},{"key":"jamc.2010070101-45","first-page":"337","article-title":"Noise Strategies for Improving Local Search. In","volume":"94","author":"B.Selman","year":"1994","journal-title":"Proceedings of AAAI"},{"key":"jamc.2010070101-46","unstructured":"Selman, B., & Kautz, K. A. (1993). Domain-Independent extensions to GSAT: Solving large structured satisfiability problems. In R. Bajcsy (Ed.), Proceedings of the international Joint Conference on Artificial Intelligence (Vol. 1, pp. 290-295). San Francisco, CA: Morgan Kaufmann Publishers Inc."},{"key":"jamc.2010070101-47","first-page":"440","article-title":"A New Method for Solving Hard Satisfiability Problems. In","volume":"92","author":"B.Selman","year":"1992","journal-title":"Proceedings of AAA"},{"key":"jamc.2010070101-48","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1090\/dimacs\/026\/17","article-title":"An improved algorithm for exact graph coloring","author":"E. C.Swell","year":"1996","journal-title":"Cliques, Coloring, and Satisfiability: 2nd DIMACS Implementation Challenge"},{"key":"jamc.2010070101-49","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-9052-5","author":"M. A. L.Thathachar","year":"2004","journal-title":"Network of Learning Automata: Techniques for On line Stochastic Optimization"},{"key":"jamc.2010070101-50","unstructured":"Thornton, J., Pham, D. N., Bain, S., & Ferreira, V., Jr. (2004). Additive versus multiplicative clause weighting for SAT. In Proceedings of the Nineteenth National Conference of Artificial Intelligence (pp. 191-196)."},{"key":"jamc.2010070101-51","author":"M. L.Tsetlin","year":"1973","journal-title":"Automaton Theory and Modeling of Biological Systems"},{"key":"jamc.2010070101-52","unstructured":"Wu, Z., & Wah, B. (2000). An efficient global-search strategy in discrete Lagrangian methods for solving hard satisfiability problems. In Proceedings of the Seventeenth National Conference on Artificial Intelligence (pp. 310-315)."},{"key":"jamc.2010070101-53","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1613\/jair.2490","article-title":"SATzilla: Portfolio-based Algorithm Selection for SAT.","volume":"32","author":"L.Xu","year":"2008","journal-title":"Journal of Artificial Intelligence Research"}],"container-title":["International Journal of Applied Metaheuristic Computing"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=47372","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T14:41:16Z","timestamp":1654094476000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/jamc.2010070101"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2010,7,1]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,7]]}},"URL":"https:\/\/doi.org\/10.4018\/jamc.2010070101","relation":{},"ISSN":["1947-8283","1947-8291"],"issn-type":[{"value":"1947-8283","type":"print"},{"value":"1947-8291","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,1]]}}}