{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T16:21:07Z","timestamp":1742401267602},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642214578"},{"type":"electronic","value":"9783642214585"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-21458-5_33","type":"book-chapter","created":{"date-parts":[[2011,6,27]],"date-time":"2011-06-27T21:11:27Z","timestamp":1309209087000},"page":"388-401","source":"Crossref","is-referenced-by-count":11,"title":["Finding Approximate and Constrained Motifs in Graphs"],"prefix":"10.1007","author":[{"given":"Riccardo","family":"Dondi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Fertin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"33_CR1","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":"A.M. 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.\u00a06478, pp. 14\u201325. Springer, Heidelberg (2010)"},{"issue":"1-2","key":"33_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-Completeness Results for Cubic Graphs. Theor. Comput. Sci.\u00a0237(1-2), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"33_CR3","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color Coding. Journal of the ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"Journal of the ACM"},{"key":"33_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-540-69068-9_6","volume-title":"Combinatorial Pattern Matching","author":"N. Betzler","year":"2008","unstructured":"Betzler, N., Fellows, M.R., Komusiewicz, C., Niedermeier, R.: Parameterized Algorithms and Hardness Results for Some Graph Motif Problems. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 31\u201343. Springer, Heidelberg (2008)"},{"key":"33_CR5","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)"},{"key":"33_CR6","unstructured":"Cesati, M.: Compendium of parameterized problems, \n                    \n                      http:\/\/bravo.ce.uniroma2.it\/home\/cesati\/research\/compendium.pdf"},{"key":"33_CR7","first-page":"27","volume-title":"ICTCS 2007","author":"R. Dondi","year":"2007","unstructured":"Dondi, R., Fertin, G., Vialette, S.: Weak Pattern Matching in Colored Graphs: Minimizing the Number of Connected Components. In: Italiano, G.F., Moggi, E., Laura, L. (eds.) ICTCS 2007, pp. 27\u201338. World Scientific, Singapore (2007)"},{"key":"33_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-642-02441-2_20","volume-title":"Combinatorial Pattern Matching","author":"R. Dondi","year":"2009","unstructured":"Dondi, R., Fertin, G., Vialette, S.: Maximum Motif Problem in Vertex-Colored Graphs. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009 Lille. LNCS, vol.\u00a05577, pp. 221\u2013235. Springer, Heidelberg (2009)"},{"key":"33_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"33_CR10","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. Fellows","year":"2007","unstructured":"Fellows, M., 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":"33_CR11","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":"20","key":"33_CR12","doi-asserted-by":"publisher","first-page":"11394","DOI":"10.1073\/pnas.1534710100","volume":"100","author":"B.P. Kelley","year":"2003","unstructured":"Kelley, B.P., Sharan, R., Karp, R.M., Sittler, T., Root, D.E., Stockwell, B.R., Ideker, T.: Conserved Pathways within Bacteria and Yeast as Revealed by Global Protein Network Alignment. Proc. Nat. Acad. Sci.\u00a0100(20), 11394\u201311399 (2003)","journal-title":"Proc. Nat. Acad. Sci."},{"key":"33_CR13","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/11415770_4","volume-title":"Research in Computational Molecular Biology","author":"M. Koyut\u00fcrk","year":"2005","unstructured":"Koyut\u00fcrk, M., Grama, A., Szpankowski, W.: Pairwise Local Alignment of Protein Interaction Networks Guided by Models of Evolution. In: Miyano, S., Mesirov, J., Kasif, S., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2005. LNCS (LNBI), vol.\u00a03500, pp. 48\u201365. Springer, Heidelberg (2005)"},{"issue":"4","key":"33_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 (TCBB)\u00a03(4), 360\u2013368 (2006)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics (TCBB)"},{"key":"33_CR15","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 University Press, Oxford (2006)"},{"key":"33_CR16","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","volume":"15","author":"A. Paz","year":"1981","unstructured":"Paz, A., Moran, S.: Non Deterministic Polynomial Optimization Problems and Their Approximations. Theor. Comput. Sci.\u00a015, 251\u2013277 (1981)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR17","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. Journal of Computational Biology\u00a013, 133\u2013144 (2006)","journal-title":"Journal of Computational Biology"},{"key":"33_CR18","first-page":"282","volume-title":"RECOMB 2004","author":"R. Sharan","year":"2004","unstructured":"Sharan, R., Ideker, T., Kelley, B., Shamir, R., Karp, R.M.: Identification of Protein Complexes by Comparative Analysis of Yeast and Bacterial Protein Interaction Data. In: Bourne, P.E., Gusfield, D. (eds.) RECOMB 2004, pp. 282\u2013289. ACM Press, New York (2004)"},{"issue":"6","key":"33_CR19","doi-asserted-by":"publisher","first-page":"1974","DOI":"10.1073\/pnas.0409522102","volume":"102","author":"R. Sharan","year":"2005","unstructured":"Sharan, R., Suthram, S., Kelley, R., Kuhn, T., McCuine, S., Uetz, P., Sittler, K.R.M., Ideker, T.: Conserved Patterns of Protein Interaction in Multiple Species. Proc. Nat. Acad. Sci.\u00a0102(6), 1974\u20131979 (2005)","journal-title":"Proc. Nat. Acad. Sci."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21458-5_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T13:48:39Z","timestamp":1553867319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21458-5_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642214578","9783642214585"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21458-5_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}