{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T04:44:26Z","timestamp":1743137066516,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319135236"},{"type":"electronic","value":"9783319135243"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13524-3_13","type":"book-chapter","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T17:51:38Z","timestamp":1417542698000},"page":"147-158","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size"],"prefix":"10.1007","author":[{"given":"Mathieu","family":"Chapelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manfred","family":"Cochefert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Romain","family":"Letourneur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,3]]},"reference":[{"issue":"3","key":"13_CR1","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1016\/j.jda.2011.03.006","volume":"9","author":"FN Abu-Khzam","year":"2011","unstructured":"Abu-Khzam, F.N., Mouawad, A.E., Liedloff, M.: An exact algorithm for connected red-blue dominating set. J. Discret. Algorithm. 9(3), 252\u2013262 (2011)","journal-title":"J. Discret. Algorithm."},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-642-17493-3_4","volume-title":"Parameterized and Exact Computation","author":"AM Ambalath","year":"2010","unstructured":"Ambalath, A.M., Balasundaram, R., Rao H., C., Koppula, V., Misra, N., Philip, G., Ramanujan, M.S.: On the kernelization complexity of colorful motifs. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 14\u201325. Springer, Heidelberg (2010)"},{"key":"13_CR3","unstructured":"Angles D\u2019Auriac, J.-A., Cohen, N., El Maftouhi, A., Harutyunyan, A., Legay, S., Manoussakis, Y.: Connected tropical subgraphs in vertex-colored graphs. http:\/\/people.maths.ox.ac.uk\/harutyunyan\/Tropical%20sets.pdf"},{"issue":"5","key":"13_CR4","doi-asserted-by":"publisher","first-page":"1296","DOI":"10.1109\/TCBB.2011.19","volume":"8","author":"N Betzler","year":"2011","unstructured":"Betzler, N., Van Bevern, R., Fellows, M.R., Komusiewicz, C., Niedermeier, R.: Parameterized algorithmics for finding connected motifs in biological networks. IEEE\/ACM Trans. Comput. Biol. Bioinf. 8(5), 1296\u20131308 (2011)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"issue":"3","key":"13_CR5","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1089\/cmb.2009.0170","volume":"17","author":"S Bruckner","year":"2010","unstructured":"Bruckner, S., H\u00fcffner, F., Karp, R.M., Shamir, R., Sharan, R.: Topology-free querying of protein interaction networks. J. Comput. Biol. 17(3), 237\u2013252 (2010)","journal-title":"J. Comput. Biol."},{"key":"13_CR6","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."},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1093\/comjnl\/bxm033","volume":"51","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.T.: The bidimensionality theory and its algorithmic applications. Comput. J. 51, 292\u2013302 (2008)","journal-title":"Comput. J."},{"issue":"1","key":"13_CR8","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.jda.2010.09.002","volume":"9","author":"R Dondi","year":"2011","unstructured":"Dondi, R., Fertin, G., Vialette, S.: Complexity issues in vertex-colored graph pattern matching. J. Discret. Algorithm. 9(1), 82\u201399 (2011)","journal-title":"J. Discret. Algorithm."},{"key":"13_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":"MR 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. 4596, pp. 340\u2013351. Springer, Heidelberg (2007)"},{"issue":"4","key":"13_CR10","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1016\/j.jcss.2010.07.003","volume":"77","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Upper and lower bounds for finding connected motifs in vertex-colored graphs. J. Comput. Syst. Sci. 77(4), 799\u2013811 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010)"},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/978-3-540-30559-0_21","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"FV Fomin","year":"2004","unstructured":"Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (Exponential) algorithms for the dominating set problem. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 245\u2013256. Springer, Heidelberg (2004)"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-540-24749-4_6","volume-title":"STACS 2004","author":"FV Fomin","year":"2004","unstructured":"Fomin, F.V., Thilikos, D.M.: A simple and fast approach for solving problems on planar graphs. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 56\u201367. Springer, Heidelberg (2004)"},{"issue":"4","key":"13_CR14","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1007\/s00453-011-9600-8","volume":"65","author":"S Guillemot","year":"2013","unstructured":"Guillemot, S., Sikora, F.: Finding and counting vertex-colored subtrees. Algorithmica 65(4), 828\u2013844 (2013)","journal-title":"Algorithmica"},{"key":"13_CR15","first-page":"367","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput\/Syst. Sci. 62, 367\u2013375 (2001)","journal-title":"J. Comput\/Syst. Sci."},{"issue":"4","key":"13_CR16","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 Trans. Comput. Biol. Bioinf. 3(4), 360\u2013368 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0895480192229273","volume":"7","author":"F McMorris","year":"1994","unstructured":"McMorris, F., Warnow, T., Wimer, T.: Triangulating vertex-colored graphs. SIAM J. Discret. Math. 7, 296\u2013306 (1994)","journal-title":"SIAM J. Discret. Math."},{"key":"13_CR18","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1007\/s00453-012-9630-x","volume":"65","author":"J Nederlof","year":"2013","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using Inclusion-Exclusion. Algorithmica 65, 868\u2013884 (2013)","journal-title":"Algorithmica"},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1089\/cmb.2006.13.133","volume":"13","author":"J Scott","year":"2006","unstructured":"Scott, J., Ideker, T., Karp, R.M., Sharan, R.: Efficient algorithms for detecting signaling pathways in protein interaction networks. J. Comput. Biol. 13, 133\u2013144 (2006)","journal-title":"J. Comput. Biol."}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13524-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T05:07:42Z","timestamp":1676005662000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13524-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319135236","9783319135243"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13524-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"3 December 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}