{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T02:33:06Z","timestamp":1787711586676,"version":"build-2784847793"},"reference-count":31,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2016,11,8]],"date-time":"2016-11-08T00:00:00Z","timestamp":1478563200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph in such a way that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR\u2010based Branch\u2010and\u2010Bound algorithm (DSATUR) is an effective exact algorithm for the VCP. One of its main drawback is that a lower bound is computed only once and it is never updated. We introduce a reduced graph which allows the computation of lower bounds at nodes of the branching tree. We compare the effectiveness of different classical VCP bounds, plus a new lower bound based on the \n<jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/net21716-math-0001.png\" xlink:title=\"urn:x-wiley:00283045:media:net21716:net21716-math-0001\"\/> \u2010to\u2010 \n<jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/net21716-math-0002.png\" xlink:title=\"urn:x-wiley:00283045:media:net21716:net21716-math-0002\"\/> mapping between VCPs and Stable Set Problems. Our new DSATUR outperforms the state of the art for random VCP instances with high density, significantly increasing the size of instances solved to proven optimality. \u00a9 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 124\u2013141 2017<\/jats:p>","DOI":"10.1002\/net.21716","type":"journal-article","created":{"date-parts":[[2016,11,8]],"date-time":"2016-11-08T12:55:35Z","timestamp":1478609735000},"page":"124-141","source":"Crossref","is-referenced-by-count":16,"title":["An Improved DSATUR\u2010Based Branch\u2010and\u2010Bound Algorithm for the Vertex Coloring Problem"],"prefix":"10.1002","volume":"69","author":[{"given":"Fabio","family":"Furini","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris\u2010Dauphine, PSL Research University, CNRS, LAMSADE 75016 Paris France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Virginie","family":"Gabrel","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris\u2010Dauphine, PSL Research University, CNRS, LAMSADE 75016 Paris France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ian\u2010Christopher","family":"Ternier","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris\u2010Dauphine, PSL Research University, CNRS, LAMSADE 75016 Paris France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2016,11,8]]},"reference":[{"key":"e_1_2_9_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:ANOR.0000032574.01332.98"},{"key":"e_1_2_9_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20218"},{"key":"e_1_2_9_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/359094.359101"},{"key":"e_1_2_9_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.1028"},{"key":"e_1_2_9_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/88616.88621"},{"key":"e_1_2_9_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-012-0042-3"},{"key":"e_1_2_9_8_1","article-title":"Solving vertex coloring problems as maximum weight stable set problems","author":"Cornaz D.","year":"2016","journal-title":"Discr Appl Math"},{"key":"e_1_2_9_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.08.002"},{"key":"e_1_2_9_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.21454"},{"key":"e_1_2_9_11_1","unstructured":"F.Furini V.Gabrel andI.\u2010C.Ternier DSATUR code Webpage Available at:www.lamsade.dauphine.fr\/coloring last accessed October 2017."},{"key":"e_1_2_9_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2016.03.020"},{"key":"e_1_2_9_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.09.010"},{"key":"e_1_2_9_14_1","volume-title":"Computers and intractability: A guide to the theory of NP\u2010completeness","author":"Garey M.","year":"1979"},{"key":"e_1_2_9_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_2_9_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1100.0436"},{"key":"e_1_2_9_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.09.064"},{"key":"e_1_2_9_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1970.tb56474.x"},{"key":"e_1_2_9_19_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.084.024"},{"key":"e_1_2_9_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.07.005"},{"key":"e_1_2_9_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2009.00696.x"},{"key":"e_1_2_9_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.4.344"},{"key":"e_1_2_9_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.11.014"},{"key":"e_1_2_9_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2014.0593"},{"key":"e_1_2_9_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130302"},{"key":"e_1_2_9_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00290-6"},{"key":"e_1_2_9_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207160701419114"},{"key":"e_1_2_9_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.10.008"},{"key":"e_1_2_9_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2010.07.019"},{"key":"e_1_2_9_30_1","volume-title":"Combinatorial optimization","author":"Schrijver A.","year":"2002"},{"key":"e_1_2_9_31_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/026\/17"},{"key":"e_1_2_9_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-008-0066-8"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.21716","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.21716","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.21716","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T20:05:48Z","timestamp":1694635548000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/net.21716"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,8]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1002\/net.21716"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/net.21716","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,8]]}}}