{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:38:28Z","timestamp":1772372308508,"version":"3.50.1"},"reference-count":8,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,6,26]],"date-time":"2009-06-26T00:00:00Z","timestamp":1245974400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2011,4]]},"DOI":"10.1007\/s10878-009-9250-9","type":"journal-article","created":{"date-parts":[[2009,6,25]],"date-time":"2009-06-25T20:39:32Z","timestamp":1245962372000},"page":"330-347","source":"Crossref","is-referenced-by-count":98,"title":["Hardness and algorithms for rainbow connection"],"prefix":"10.1007","volume":"21","author":[{"given":"Sourav","family":"Chakraborty","sequence":"first","affiliation":[]},{"given":"Eldar","family":"Fischer","sequence":"additional","affiliation":[]},{"given":"Arie","family":"Matsliah","sequence":"additional","affiliation":[]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,6,26]]},"reference":[{"key":"9250_CR1","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The probabilistic method","author":"N Alon","year":"2000","unstructured":"Alon N, Spencer JH (2000) The probabilistic method, 2nd edn. Wiley, New York","edition":"2"},{"key":"9250_CR2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1006\/jagm.1994.1005","volume":"16","author":"N Alon","year":"1994","unstructured":"Alon N, Duke RA, Lefmann H, R\u00f6dl V, Yuster R (1994) The algorithmic aspects of the Regularity Lemma. J Algorithms 16:80\u2013109","journal-title":"J Algorithms"},{"issue":"1","key":"9250_CR3","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0020-0190(96)00190-1","volume":"61","author":"A Blum","year":"1997","unstructured":"Blum A, Karger D (1997) An $\\tilde{O}(n^{3\/14})$ -coloring algorithm for 3-colorable graphs. Inf Process Lett 61(1):49\u201353","journal-title":"Inf Process Lett"},{"key":"9250_CR4","doi-asserted-by":"crossref","unstructured":"Caro Y, Lev A, Roditty Y, Tuza Z, Yuster R (2008) On rainbow connection, Electron J Comb 15, Paper R57","DOI":"10.37236\/781"},{"issue":"1","key":"9250_CR5","doi-asserted-by":"crossref","first-page":"85","DOI":"10.21136\/MB.2008.133947","volume":"133","author":"G Chartrand","year":"2008","unstructured":"Chartrand G, Johns GL, McKeon KA, Zhang P (2008) Rainbow connection in graphs. Math Bohem 133(1):85\u201398","journal-title":"Math Bohem"},{"key":"9250_CR6","doi-asserted-by":"crossref","unstructured":"Fischer E, Matsliah A, Shapira A (2007) Approximate hypergraph partitioning and applications. In: Proceedings of the 48th annual IEEE symposium on foundations of computer science (FOCS), pp\u00a0579\u2013589","DOI":"10.1109\/FOCS.2007.12"},{"key":"9250_CR7","unstructured":"Koml\u00f3s J, Simonovits M (1996) Szemer\u00e9di\u2019s Regularity Lemma and its applications in graph theory. In: Mikl\u00f3s, D, S\u00f3s, VT, Sz\u00f6nyi, T (eds) Combinatorics, Paul Erd\u00f6s is Eighty. Bolyai society mathematical studies, vol\u00a02. Budapest, pp\u00a0295\u2013352"},{"key":"9250_CR8","first-page":"399","volume-title":"Proc. colloque inter. CNRS 260","author":"E Szemer\u00e9di","year":"1978","unstructured":"Szemer\u00e9di E (1978) Regular partitions of graphs. In: Proc. colloque inter. CNRS 260. CNRS, Paris, pp\u00a0399\u2013401."}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9250-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9250-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9250-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,7]],"date-time":"2021-10-07T21:07:18Z","timestamp":1633640838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9250-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,26]]},"references-count":8,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["9250"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9250-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6,26]]}}}