{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T07:49:32Z","timestamp":1743148172780,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030592660"},{"type":"electronic","value":"9783030592677"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-59267-7_33","type":"book-chapter","created":{"date-parts":[[2020,10,11]],"date-time":"2020-10-11T19:02:33Z","timestamp":1602442953000},"page":"390-401","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of the Partition Coloring Problem"],"prefix":"10.1007","author":[{"given":"Zhenyu","family":"Guo","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1012-2373","authenticated-orcid":false,"given":"Mingyu","family":"Xiao","sequence":"additional","affiliation":[]},{"given":"Yi","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,10,9]]},"reference":[{"key":"33_CR1","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets m\u00f6bius: fast subset convolution. In: Proceedings of the Thirty-Ninth Annual ACM symposium on Theory of computing, pp. 67\u201374. ACM (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"33_CR2","unstructured":"Cauchy, A.L.B.: Cours d\u2019analyse de l\u2019\u00c9cole Royale Polytechnique. Debure (1821)"},{"issue":"2","key":"33_CR3","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/s10878-019-00388-z","volume":"38","author":"P Damaschke","year":"2019","unstructured":"Damaschke, P.: Parameterized mixed graph coloring. J. Comb. Optim. 38(2), 362\u2013374 (2019)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"33_CR4","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.ejor.2014.05.011","volume":"240","author":"M Demange","year":"2015","unstructured":"Demange, M., Ekim, T., Ries, B., Tanasescu, C.: On some applications of the selective graph coloring problem. Eur. J. Oper. Res. 240(2), 307\u2013314 (2015)","journal-title":"Eur. J. Oper. Res."},{"key":"33_CR5","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.tcs.2013.04.018","volume":"540","author":"M Demange","year":"2014","unstructured":"Demange, M., Monnot, J., Pop, P., Ries, B.: On the complexity of the selective graph coloring problem in some special classes of graphs. Theoret. Comput. Sci. 540, 89\u2013102 (2014)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"33_CR6","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theoret. Comput. Sci. 141(1\u20132), 109\u2013131 (1995)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"33_CR7","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s10878-005-4103-7","volume":"10","author":"T Ekim","year":"2005","unstructured":"Ekim, T., de Werra, D.: On split-coloring problems. J. Comb. Optim. 10(3), 211\u2013225 (2005). https:\/\/doi.org\/10.1007\/s10878-005-4103-7","journal-title":"J. Comb. Optim."},{"issue":"3","key":"33_CR8","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1002\/net.20365","volume":"55","author":"Y Frota","year":"2010","unstructured":"Frota, Y., Maculan, N., Noronha, T.F., Ribeiro, C.C.: A branch-and-cut algorithm for partition coloring. Networks 55(3), 194\u2013204 (2010)","journal-title":"Networks"},{"key":"33_CR9","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.cor.2017.12.019","volume":"92","author":"F Furini","year":"2018","unstructured":"Furini, F., Malaguti, E., Santini, A.: An exact algorithm for the partition coloring problem. Comput. Oper. Res. 92, 170\u2013181 (2018)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"33_CR10","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1023\/A:1009823419804","volume":"3","author":"P Galinier","year":"1999","unstructured":"Galinier, P., Hao, J.K.: Hybrid evolutionary algorithms for graph coloring. J. Comb. Optim. 3(4), 379\u2013397 (1999). https:\/\/doi.org\/10.1023\/A:1009823419804","journal-title":"J. Comb. Optim."},{"issue":"1","key":"33_CR11","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1109\/T-VT.1986.24063","volume":"35","author":"A Gamst","year":"1986","unstructured":"Gamst, A.: Some lower bounds for a class of frequency assignment problems. IEEE Trans. Veh. Technol. 35(1), 8\u201314 (1986)","journal-title":"IEEE Trans. Veh. Technol."},{"issue":"3","key":"33_CR12","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1023\/A:1027312403532","volume":"7","author":"CA Glass","year":"2003","unstructured":"Glass, C.A., Pr\u00fcgel-Bennett, A.: Genetic algorithm for graph coloring: exploration of Galinier and Hao\u2019s algorithm. J. Comb. Optim. 7(3), 229\u2013236 (2003). https:\/\/doi.org\/10.1023\/A:1027312403532","journal-title":"J. Comb. Optim."},{"issue":"1","key":"33_CR13","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF01194253","volume":"45","author":"P Hansen","year":"1997","unstructured":"Hansen, P., Kuplinsky, J., de Werra, D.: Mixed graph colorings. Math. Methods Oper. Res. 45(1), 145\u2013160 (1997). https:\/\/doi.org\/10.1007\/BF01194253","journal-title":"Math. Methods Oper. Res."},{"issue":"4","key":"33_CR14","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"33_CR15","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.orl.2011.02.006","volume":"39","author":"EA Hoshino","year":"2011","unstructured":"Hoshino, E.A., Frota, Y.A., De Souza, C.C.: A branch-and-price approach for the partition coloring problem. Oper. Res. Lett. 39(2), 132\u2013137 (2011)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"33_CR16","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10462-016-9485-7","volume":"47","author":"Y Jin","year":"2016","unstructured":"Jin, Y., Hamiez, J.-P., Hao, J.-K.: Algorithms for the minimum sum coloring problem: a review. Artif. Intell. Rev. 47(3), 367\u2013394 (2016). https:\/\/doi.org\/10.1007\/s10462-016-9485-7","journal-title":"Artif. Intell. Rev."},{"key":"33_CR17","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85\u2013103 (1972). Springer, Boston. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1\u20132","key":"33_CR18","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1002\/malq.19670130104","volume":"13","author":"MR Krom","year":"1967","unstructured":"Krom, M.R.: The decision problem for a class of first-order formulas in which all disjunctions are binary. Math. Logic Q. 13(1\u20132), 15\u201320 (1967)","journal-title":"Math. Logic Q."},{"key":"33_CR19","doi-asserted-by":"crossref","unstructured":"Kubicka, E., Schwenk, A.J.: An introduction to chromatic sums. In: Proceedings of the 17th Conference on ACM Annual Computer Science Conference, pp. 39\u201345. ACM (1989)","DOI":"10.1145\/75427.75430"},{"key":"33_CR20","unstructured":"Li, G., Simha, R.: The partition coloring problem and its application to wavelength routing and assignment. In: Proceedings of the First Workshop on Optical Networks, p. 1. Citeseer (2000)"},{"key":"33_CR21","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/j.cor.2019.05.010","volume":"109","author":"W Lin","year":"2019","unstructured":"Lin, W., Xiao, M., Zhou, Y., Guo, Z.: Computing lower bounds for minimum sum coloring and optimum cost chromatic partition. Comput. Oper. Res. 109, 263\u2013272 (2019)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"33_CR22","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s10878-009-9223-z","volume":"20","author":"G Lucarelli","year":"2010","unstructured":"Lucarelli, G., Milis, I., Paschos, V.T.: On the max-weight edge coloring problem. J. Comb. Optim. 20(4), 429\u2013442 (2010). https:\/\/doi.org\/10.1007\/s10878-009-9223-z","journal-title":"J. Comb. Optim."},{"key":"33_CR23","doi-asserted-by":"publisher","unstructured":"Pop, P.C., Hu, B., Raidl, G.R.: A memetic algorithm with two distinct solution representations for the partition graph coloring problem. In: Moreno-Diaz, R., Pichler, F., Quesada-Arencibia, A. (eds.) Computer Aided Systems Theory - EUROCAST 2013. EUROCAST 2013. Lecture Notes in Computer Science, vol. 8111, pp. 219\u2013226. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-53856-8_28","DOI":"10.1007\/978-3-642-53856-8_28"},{"issue":"1","key":"33_CR24","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1023\/B:JOCO.0000021940.40066.0c","volume":"8","author":"X Zhou","year":"2004","unstructured":"Zhou, X., Nishizeki, T.: Algorithm for the cost edge-coloring of trees. J. Comb. Optim. 8(1), 97\u2013108 (2004). https:\/\/doi.org\/10.1023\/B:JOCO.0000021940.40066.0c","journal-title":"J. Comb. Optim."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-59267-7_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T20:06:12Z","timestamp":1723752372000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-59267-7_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030592660","9783030592677"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-59267-7_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"9 October 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TAMC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Theory and Applications of Models of Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Changsha","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 October 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 October 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tamc2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/tamc2020.csu.edu.cn\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"83","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"45% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}