{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T09:47:25Z","timestamp":1764841645595,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642174926"},{"type":"electronic","value":"9783642174933"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-17493-3_4","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T08:41:01Z","timestamp":1291365661000},"page":"14-25","source":"Crossref","is-referenced-by-count":20,"title":["On the Kernelization Complexity of Colorful Motifs"],"prefix":"10.1007","author":[{"given":"Abhimanyu M.","family":"Ambalath","sequence":"first","affiliation":[]},{"given":"Radheshyam","family":"Balasundaram","sequence":"additional","affiliation":[]},{"given":"Chintan","family":"Rao H.","sequence":"additional","affiliation":[]},{"given":"Venkata","family":"Koppula","sequence":"additional","affiliation":[]},{"given":"Neeldhara","family":"Misra","sequence":"additional","affiliation":[]},{"given":"Geevarghese","family":"Philip","sequence":"additional","affiliation":[]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Ambalath, A.M., Balasundaram, R., Chintan Rao, H., Koppula, V., Misra, N., Philip, G., Ramanujan, M.S.: On the kernelization complexity of colorful motifs (2010), http:\/\/www.imsc.res.in\/~gphilip\/publications\/cm.pdf [Full Version]","DOI":"10.1007\/978-3-642-17493-3_4"},{"issue":"8","key":"4_CR2","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. Journal of Computer and System Sciences\u00a075(8), 423\u2013434 (2009)","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/978-3-642-04128-0_57","volume-title":"Algorithms - ESA 2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 635\u2013646. Springer, Heidelberg (2009)"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/978-3-642-02008-7_6","volume-title":"Research in Computational Molecular Biology","author":"S. Bruckner","year":"2009","unstructured":"Bruckner, S., H\u00fcffner, F., Karp, R.M., Shamir, R., Sharan, R.: Topology-free querying of protein interaction networks. In: Batzoglou, S. (ed.) RECOMB 2009. LNCS, vol.\u00a05541, pp. 74\u201389. Springer, Heidelberg (2009)"},{"issue":"1","key":"4_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2005.01.002","volume":"198","author":"J.-y. Cai","year":"2005","unstructured":"Cai, J.-y., Chakaravarthy, V.T., Hemaspaandra, L.A., Ogihara, M.: Competing provers yield improved Karp-Lipton collapse results. Information and Computation\u00a0198(1), 1\u201323 (2005)","journal-title":"Information and Computation"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Kernelization hardness of connectivity problems in d-degenerate graphs. Accepted at WG 2010 (2010)","DOI":"10.1007\/978-3-642-16926-7_15"},{"key":"4_CR7","series-title":"LNCS","first-page":"378","volume-title":"Proceedings of ICALP 2009","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through Colors and IDs. In: Proceedings of ICALP 2009. LNCS, vol.\u00a05555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"key":"4_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-540-73420-8_31","volume-title":"Automata, Languages and Programming","author":"M.R. Fellows","year":"2007","unstructured":"Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 340\u2013351. Springer, Heidelberg (2007)"},{"key":"4_CR10","unstructured":"Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: On out-trees with many leaves. In: Proceedings of STACS 2009, pp. 421\u2013432 (2009)"},{"key":"4_CR11","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"4_CR12","first-page":"133","volume-title":"Proceedings of STOC 2008","author":"L. Fortnow","year":"2008","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Proceedings of STOC 2008, pp. 133\u2013142. ACM, New York (2008)"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-3-642-15155-2_36","volume-title":"Mathematical Foundations of Computer Science 2010","author":"S. Guillemot","year":"2010","unstructured":"Guillemot, S., Sikora, F.: Finding and counting vertex-colored subtrees. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol.\u00a06281, pp. 405\u2013416. Springer, Heidelberg (2010)"},{"issue":"4","key":"4_CR14","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1109\/TCBB.2006.55","volume":"3","author":"V. Lacroix","year":"2006","unstructured":"Lacroix, V., Fernandes, C.G., Sagot, M.-F.: Motif search in graphs: Application to metabolic networks. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a03(4), 360\u2013368 (2006)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"4_CR15","unstructured":"Lokshtanov, D.: New Methods in Parameterized Algorithms and Complexity. PhD thesis, University of Bergen, Norway (2009)"},{"key":"4_CR16","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17493-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T15:38:59Z","timestamp":1559835539000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17493-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642174926","9783642174933"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17493-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}