{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:44:59Z","timestamp":1774417499631,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T00:00:00Z","timestamp":1581552000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T00:00:00Z","timestamp":1581552000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Agence National de la Recherche","award":["DEMOGRAPH (ANR-16-CE40-0028)"],"award-info":[{"award-number":["DEMOGRAPH (ANR-16-CE40-0028)"]}]},{"name":"Agence National de la Recherche","award":["ESIGMA (ANR-17-CE23-0010)"],"award-info":[{"award-number":["ESIGMA (ANR-17-CE23-0010)"]}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["306262\/2014-2"],"award-info":[{"award-number":["306262\/2014-2"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["311013\/2015-5"],"award-info":[{"award-number":["311013\/2015-5"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["Universal 421660\/2016-3"],"award-info":[{"award-number":["Universal 421660\/2016-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["Universal 401519\/2016-3"],"award-info":[{"award-number":["Universal 401519\/2016-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005283","name":"Funcap","doi-asserted-by":"crossref","award":["PNE-0112-00061.01.00\/16"],"award-info":[{"award-number":["PNE-0112-00061.01.00\/16"]}],"id":[{"id":"10.13039\/501100005283","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002322","name":"CAPES","doi-asserted-by":"crossref","award":["Finance Code 001"],"award-info":[{"award-number":["Finance Code 001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,8]]},"DOI":"10.1007\/s00453-020-00686-7","type":"journal-article","created":{"date-parts":[[2020,2,13]],"date-time":"2020-02-13T07:12:22Z","timestamp":1581577942000},"page":"2316-2336","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Dual Parameterization of Weighted Coloring"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7074-2753","authenticated-orcid":false,"given":"J\u00falio","family":"Ara\u00fajo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2730-4640","authenticated-orcid":false,"given":"Victor A.","family":"Campos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6666-0533","authenticated-orcid":false,"given":"Carlos Vin\u00edcius G. C.","family":"Lima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4608-4559","authenticated-orcid":false,"given":"Vin\u00edcius Fernandes","family":"dos Santos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8981-9287","authenticated-orcid":false,"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8917-0564","authenticated-orcid":false,"given":"Ana","family":"Silva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,13]]},"reference":[{"key":"686_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.tcs.2018.03.013","volume":"729","author":"J Ara\u00fajo","year":"2018","unstructured":"Ara\u00fajo, J., Baste, J., Sau, I.: Ruling out FPT algorithms for weighted coloring on forests. Theor. Comput. Sci. 729, 11\u201319 (2018)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"686_CR2","doi-asserted-by":"publisher","first-page":"2029","DOI":"10.1137\/140954167","volume":"28","author":"J Ara\u00fajo","year":"2014","unstructured":"Ara\u00fajo, J., Nisse, N., P\u00e9rennes, S.: Weighted coloring in trees. SIAM J. Discrete Math. 28(4), 2029\u20132041 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"686_CR3","doi-asserted-by":"publisher","first-page":"1401","DOI":"10.1137\/15M1039584","volume":"30","author":"M Basavaraju","year":"2016","unstructured":"Basavaraju, M., Francis, M.C., Ramanujan, M.S., Saurabh, S.: Partially polynomial kernels for set cover and test cover. SIAM J. Discrete Math. 30(3), 1401\u20131423 (2016)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"686_CR4","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion\u2013exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"686_CR5","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"686_CR6","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"35","key":"686_CR7","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"686_CR8","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1051\/ro\/2016018","volume":"51","author":"\u00c9 Bonnet","year":"2017","unstructured":"Bonnet, \u00c9., Paschos, V.T.: Dual parameterization and parameterized approximability of subset graph problems. RAIRO Oper. Res. 51(1), 261\u2013266 (2017)","journal-title":"RAIRO Oper. Res."},{"key":"686_CR9","doi-asserted-by":"crossref","unstructured":"Chor, B., Fellows, M., Juedes, D.W.: Linear kernels in linear time, or how to save $$k$$ colors in $$O(n^2)$$ steps. In: Procedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol. 3353 of LNCS, pp. 257\u2013269 (2004)","DOI":"10.1007\/978-3-540-30559-0_22"},{"key":"686_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"4","key":"686_CR11","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1016\/j.dam.2008.06.013","volume":"157","author":"D de Werra","year":"2009","unstructured":"de Werra, D., Demange, M., Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring on planar, bipartite and split graphs: complexity and approximation. Discrete Appl. Math. 157(4), 819\u2013832 (2009)","journal-title":"Discrete Appl. Math."},{"key":"686_CR12","doi-asserted-by":"crossref","unstructured":"Demange, M., de Werra, D., Monnot, J., Paschos, V.T.: Weighted node coloring: when stable sets are expensive. In: Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol. 2573 of LNCS, pp. 114\u2013125. Springer (2002)","DOI":"10.1007\/3-540-36379-3_11"},{"issue":"1","key":"686_CR13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(94)90039-6","volume":"50","author":"M Demange","year":"1994","unstructured":"Demange, M., Grisoni, P., Paschos, V.T.: Approximation results for the minimum graph coloring problem. Inf. Process. Lett. 50(1), 19\u201323 (1994)","journal-title":"Inf. Process. Lett."},{"key":"686_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, vol. 173, 4th edn. Springer, Berlin (2010)","edition":"4"},{"issue":"2","key":"686_CR15","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and IDs. ACM Trans. Algorithms 11(2), 13:1\u201313:20 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"686_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"key":"686_CR17","doi-asserted-by":"crossref","unstructured":"Duh, R., F\u00fcrer, M.: Approximation of $$k$$-set cover by semi-local optimization. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC), pp. 256\u2013264 (1997)","DOI":"10.1145\/258533.258599"},{"key":"686_CR18","doi-asserted-by":"crossref","unstructured":"Escoffier, B.: Saving colors and max coloring: some fixed-parameter tractability results. In: Proceedings of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG). LNCS, vol. 9941, pp. 50\u201361 (2016)","DOI":"10.1007\/978-3-662-53536-3_5"},{"issue":"3","key":"686_CR19","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.ipl.2005.09.013","volume":"97","author":"B Escoffier","year":"2006","unstructured":"Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring: further complexity and approximability results. Inf. Process. Lett. 97(3), 98\u2013103 (2006)","journal-title":"Inf. Process. Lett."},{"key":"686_CR20","volume-title":"Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2010)"},{"issue":"1","key":"686_CR21","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"686_CR22","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D Fulkerson","year":"1965","unstructured":"Fulkerson, D., Gross, O.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"key":"686_CR23","doi-asserted-by":"publisher","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P Gilmore","year":"1964","unstructured":"Gilmore, P., Hoffman, A.: A characterization of comparability graphs and of interval graphs. Can. J. Math. 16, 539\u2013548 (1964)","journal-title":"Can. J. Math."},{"issue":"2","key":"686_CR24","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0020-0190(97)00002-1","volume":"61","author":"DJ Guan","year":"1997","unstructured":"Guan, D.J., Zhu, X.: A coloring problem for weighted graphs. Inf. Process. Lett. 61(2), 77\u201381 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"41","key":"686_CR25","doi-asserted-by":"publisher","first-page":"5744","DOI":"10.1016\/j.tcs.2011.06.018","volume":"412","author":"GZ Gutin","year":"2011","unstructured":"Gutin, G.Z., Jones, M., Yeo, A.: Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems. Theor. Comput. Sci. 412(41), 5744\u20135751 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"686_CR26","unstructured":"Halld\u00f3rsson, M.M.: Approximating discrete collections via local improvements. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 160\u2013169 (1995)"},{"key":"686_CR27","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M.: Approximating $$k$$-set cover and complementary graph coloring. In: Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization (IPCO). LNCS, vol. 1084, pp. 118\u2013131 (1996)","DOI":"10.1007\/3-540-61310-2_10"},{"issue":"2","key":"686_CR28","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0020-0190(94)00113-8","volume":"52","author":"R Hassin","year":"1994","unstructured":"Hassin, R., Lahav, S.: Maximizing the number of unused colors in the vertex coloring problem. Inf. Process. Lett. 52(2), 87\u201390 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"686_CR29","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1007\/s00453-011-9604-4","volume":"65","author":"F Havet","year":"2013","unstructured":"Havet, F., Sampaio, L.: On the grundy and $$b$$-chromatic numbers of a graph. Algorithmica 65(4), 885\u2013899 (2013)","journal-title":"Algorithmica"},{"key":"686_CR30","doi-asserted-by":"crossref","unstructured":"Hermelin, D., Wu, X.: Weak compositions and their applications to polynomial lower bounds for kernelization. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 104\u2013113 (2012)","DOI":"10.1137\/1.9781611973099.9"},{"issue":"2","key":"686_CR31","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"686_CR32","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"686_CR33","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"686_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10878-010-9290-1","volume":"24","author":"T Kavitha","year":"2012","unstructured":"Kavitha, T., Mestre, J.: Max-coloring paths: tight bounds and extensions. J. Comb. Optim. 24(1), 1\u201314 (2012)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"686_CR35","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"EL Lawler","year":"1976","unstructured":"Lawler, E.L.: A note on the complexity of the chromatic number problem. Inf. Process. Lett. 5(3), 66\u201367 (1976)","journal-title":"Inf. Process. Lett."},{"issue":"7\u20138","key":"686_CR36","doi-asserted-by":"publisher","first-page":"1037","DOI":"10.1016\/j.dam.2012.11.005","volume":"161","author":"MC Lin","year":"2013","unstructured":"Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.: Normal helly circular-arc graphs and its subclasses. Discrete Appl. Math. 161(7\u20138), 1037\u20131059 (2013)","journal-title":"Discrete Appl. Math."},{"issue":"18","key":"686_CR37","doi-asserted-by":"publisher","first-page":"5618","DOI":"10.1016\/j.disc.2008.04.003","volume":"309","author":"MC Lin","year":"2009","unstructured":"Lin, M.C., Szwarcfiter, J.L.: Characterizations and recognition of circular-arc graphs and subclasses: a survey. Discrete Math. 309(18), 5618\u20135635 (2009)","journal-title":"Discrete Math."},{"key":"686_CR38","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"key":"686_CR39","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1064546.1180619","volume":"10","author":"SV Pemmaraju","year":"2005","unstructured":"Pemmaraju, S.V., Penumatcha, S., Raman, R.: Approximating interval coloring and max-coloring in chordal graphs. ACM J. Exp. Algorithmics 10, 2\u20138 (2005)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"2","key":"686_CR40","doi-asserted-by":"publisher","first-page":"535","DOI":"10.2140\/pjm.1971.39.535","volume":"39","author":"A Tucker","year":"1971","unstructured":"Tucker, A.: Matrix characterizations of circular-arc graphs. Pac. J. Math. 39(2), 535\u2013545 (1971)","journal-title":"Pac. J. Math."},{"key":"686_CR41","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C Yap","year":"1983","unstructured":"Yap, C.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287\u2013300 (1983)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00686-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00686-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00686-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T00:37:52Z","timestamp":1613090272000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00686-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,13]]},"references-count":41,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["686"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00686-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,13]]},"assertion":[{"value":"29 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}