{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T04:11:25Z","timestamp":1751947885873},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319295152"},{"type":"electronic","value":"9783319295169"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-29516-9_18","type":"book-chapter","created":{"date-parts":[[2016,2,19]],"date-time":"2016-02-19T05:05:19Z","timestamp":1455858319000},"page":"209-220","source":"Crossref","is-referenced-by-count":2,"title":["On the Complexity of Rainbow Coloring Problems"],"prefix":"10.1007","author":[{"given":"Eduard","family":"Eiben","sequence":"first","affiliation":[]},{"given":"Robert","family":"Ganian","sequence":"additional","affiliation":[]},{"given":"Juho","family":"Lauri","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,2,20]]},"reference":[{"key":"18_CR1","unstructured":"Ananth, P., Nasre, M., Sarpatwar, K.K.: Rainbow connectivity: hardness and tractability. In: FSTTCS 2011, pp. 241\u2013251 (2011)"},{"issue":"1","key":"18_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1993.1001","volume":"14","author":"H Bodlaender","year":"1993","unstructured":"Bodlaender, H.: On linear time minor tests with depth-first search. J. Algorithms 14(1), 1\u201323 (1993)","journal-title":"J. Algorithms"},{"issue":"2","key":"18_CR3","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"issue":"3","key":"18_CR4","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/s10878-009-9250-9","volume":"21","author":"S Chakraborty","year":"2009","unstructured":"Chakraborty, S., Fischer, E., Matsliah, A., Yuster, R.: Hardness and algorithms for rainbow connection. J. Comb. Optimizat. 21(3), 330\u2013347 (2009)","journal-title":"J. Comb. Optimizat."},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-642-32241-9_16","volume-title":"Computing and Combinatorics","author":"LS Chandran","year":"2012","unstructured":"Chandran, L.S., Rajendraprasad, D.: Rainbow colouring of split and threshold graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 181\u2013192. Springer, Heidelberg (2012)"},{"key":"18_CR6","unstructured":"Chandran, L.S., Rajendraprasad, D.: Inapproximability of rainbow colouring. In: FSTTCS 2013, pp. 153\u2013162 (2013)"},{"issue":"1","key":"18_CR7","doi-asserted-by":"crossref","first-page":"85","DOI":"10.21136\/MB.2008.133947","volume":"133","author":"G Chartrand","year":"2008","unstructured":"Chartrand, G., Johns, G., McKeon, K., Zhang, P.: Rainbow connection in graphs. Mathematica Bohemica 133(1), 85\u201398 (2008)","journal-title":"Mathematica Bohemica"},{"key":"18_CR8","doi-asserted-by":"publisher","DOI":"10.1201\/9781584888017","volume-title":"Chromatic Graph Theory","author":"G Chartrand","year":"2008","unstructured":"Chartrand, G., Zhang, P.: Chromatic Graph Theory. CRC Press, Boca Raton (2008)"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.tcs.2013.02.012","volume":"481","author":"L Chen","year":"2013","unstructured":"Chen, L., Li, X., Lian, H.: Further hardness results on the rainbow vertex-connection number of graphs. Theoret. Comput. Sci. 481, 18\u201323 (2013)","journal-title":"Theoret. Comput. Sci."},{"issue":"35","key":"18_CR10","doi-asserted-by":"publisher","first-page":"4531","DOI":"10.1016\/j.tcs.2011.04.032","volume":"412","author":"L Chen","year":"2011","unstructured":"Chen, L., Li, X., Shi, Y.: The complexity of determining the rainbow vertex-connection of a graph. Theoret. Comput. Sci. 412(35), 4531\u20134535 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Inf. Comput. 85, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"issue":"2","key":"18_CR12","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"key":"18_CR13","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. Springer, Heidelberg (2010)"},{"key":"18_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013)"},{"issue":"7","key":"18_CR15","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1016\/j.dam.2009.10.018","volume":"158","author":"R Ganian","year":"2010","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P.: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discrete App. Math. 158(7), 851\u2013867 (2010)","journal-title":"Discrete App. Math."},{"issue":"4","key":"18_CR16","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.ipl.2007.03.005","volume":"103","author":"G Gottlob","year":"2007","unstructured":"Gottlob, G., Lee, S.T.: A logical approach to multicut problems. Inf. Process. Lett. 103(4), 136\u2013141 (2007)","journal-title":"Inf. Process. Lett."},{"key":"18_CR17","unstructured":"Keranen, M., Lauri, J.: Computing minimum rainbow, strong rainbow colorings of block graphs. Preprint available on arXiv:1405.6893 (2014)"},{"issue":"3","key":"18_CR18","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1002\/jgt.20418","volume":"63","author":"M Krivelevich","year":"2010","unstructured":"Krivelevich, M., Yuster, R.: The rainbow connection of a graph is (at most) reciprocal to its minimum degree. J. Graph Theory 63(3), 185\u2013191 (2010)","journal-title":"J. Graph Theory"},{"key":"18_CR19","unstructured":"Lauri, J.: Further hardness results for rainbow and strong rainbow connectivity. Discrete Appl. Math. (to appear)"},{"key":"18_CR20","first-page":"213","volume":"93","author":"X Li","year":"2014","unstructured":"Li, X., Mao, Y., Shi, Y.: The strong rainbow vertex-connection of graphs. Utilitas Mathematica 93, 213\u2013223 (2014)","journal-title":"Utilitas Mathematica"},{"issue":"1","key":"18_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-012-1243-2","volume":"29","author":"X Li","year":"2012","unstructured":"Li, X., Shi, Y., Sun, Y.: Rainbow connections of graphs: a survey. Graphs Comb. 29(1), 1\u201338 (2012)","journal-title":"Graphs Comb."},{"key":"18_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-3119-0","volume-title":"Rainbow Connections of Graphs","author":"X Li","year":"2012","unstructured":"Li, X., Sun, Y.: Rainbow Connections of Graphs. Springer, New York (2012)"},{"issue":"3","key":"18_CR23","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"issue":"2","key":"18_CR24","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1002\/jgt.20643","volume":"71","author":"LS Chandran","year":"2012","unstructured":"Chandran, L.S., Das, A., Rajendraprasad, D., Varma, N.M.: Rainbow connection number, connected dominating sets. J. Graph Theory 71(2), 206\u2013218 (2012)","journal-title":"J. Graph Theory"},{"issue":"2","key":"18_CR25","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00453-012-9689-4","volume":"67","author":"K Uchizawa","year":"2013","unstructured":"Uchizawa, K., Aoki, T., Ito, T., Suzuki, A., Zhou, X.: On the rainbow connectivity of graphs: complexity and FPT algorithms. Algorithmica 67(2), 161\u2013179 (2013)","journal-title":"Algorithmica"},{"key":"18_CR26","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic umber. In: STOC 2006, pp. 681\u2013690 (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-29516-9_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,14]],"date-time":"2024-06-14T13:03:23Z","timestamp":1718370203000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-29516-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319295152","9783319295169"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-29516-9_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}