{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:27Z","timestamp":1759637907973},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540690665"},{"type":"electronic","value":"9783540690689"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69068-9_6","type":"book-chapter","created":{"date-parts":[[2008,6,7]],"date-time":"2008-06-07T05:54:28Z","timestamp":1212818068000},"page":"31-43","source":"Crossref","is-referenced-by-count":22,"title":["Parameterized Algorithms and Hardness Results for Some Graph Motif Problems"],"prefix":"10.1007","author":[{"given":"Nadja","family":"Betzler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"6_CR1","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0959-440X(03)00031-9","volume":"13","author":"E. Alm","year":"2003","unstructured":"Alm, E., Arkin, A.P.: Biological networks. Curr. Opin. Struc. Biol.\u00a013(2), 193\u2013202 (2003)","journal-title":"Curr. Opin. Struc. Biol."},{"issue":"4","key":"6_CR2","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. J. ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"6_CR3","first-page":"67","volume-title":"Proc.\u00a039th STOC","author":"A. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: Proc.\u00a039th STOC, pp. 67\u201374. ACM, New York (2007)"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(01)00207-1","volume":"81","author":"M. Cesati","year":"2002","unstructured":"Cesati, M.: Perfect code is W[1]-complete. Inform. Process. Lett.\u00a081, 163\u2013168 (2002)","journal-title":"Inform. Process. Lett."},{"key":"6_CR5","unstructured":"Deshpande, P., Barzilay, R., Karger, D.R.: Randomized decoding for selection-and-ordering problems. In: Proc. NAACL HLT 2007. Association for Computational Linguistics, pp. 444\u2013451 (2007)"},{"key":"6_CR6","series-title":"WSPC","first-page":"27","volume-title":"Proc.\u00a010th\u00a0ICTCS","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: Proc.\u00a010th\u00a0ICTCS. WSPC, vol.\u00a04596, pp. 27\u201338. World Scientific, Singapore (2007)"},{"key":"6_CR7","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-71681-5_1","volume-title":"Research in Computational Molecular Biology","author":"B. Dost","year":"2007","unstructured":"Dost, B., Shlomi, T., Gupta, N., Ruppin, E., Bafna, V., Sharan, R.: QNet: A tool for querying protein interaction networks. In: Speed, T., Huang, H. (eds.) RECOMB 2007. LNCS (LNBI), vol.\u00a04453, pp. 1\u201315. Springer, Heidelberg (2007)"},{"key":"6_CR8","doi-asserted-by":"crossref","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":"6_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":"#cr-split#-6_CR10.1","doi-asserted-by":"crossref","unstructured":"H\u00fcffner, F., Wernicke, S., Zichner, T.: Algorithm engineering for color-coding to facilitate signaling pathway detection. In: Proc.\u00a05th\u00a0APBC. Advances in Bioinf. and Comput. Biol., vol.\u00a05, pp. 277\u2013286. Imperial College Press (2007);","DOI":"10.1142\/9781860947995_0030"},{"key":"#cr-split#-6_CR10.2","unstructured":"Extended version to appear in Algorithmica"},{"issue":"13","key":"6_CR11","doi-asserted-by":"publisher","first-page":"1708","DOI":"10.1093\/bioinformatics\/btm160","volume":"23","author":"F. H\u00fcffner","year":"2007","unstructured":"H\u00fcffner, F., Wernicke, S., Zichner, T.: FASPAD: fast signaling pathway detection. Bioinformatics\u00a023(13), 1708\u20131709 (2007)","journal-title":"Bioinformatics"},{"key":"6_CR12","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/11557067_15","volume-title":"Algorithms in Bioinformatics","author":"V. Lacroix","year":"2005","unstructured":"Lacroix, V., Fernandes, C.G., Sagot, M.-F.: Reaction motifs in metabolic networks. In: Casadio, R., Myers, G. (eds.) WABI 2005. LNCS (LNBI), vol.\u00a03692, pp. 178\u2013191. Springer, Heidelberg (2005)"},{"key":"6_CR13","doi-asserted-by":"crossref","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)"},{"issue":"2","key":"6_CR14","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.\u00a013(2), 133\u2013144 (2006)","journal-title":"J. Comput. Biol."},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1038\/nbt1196","volume":"24","author":"R. Sharan","year":"2006","unstructured":"Sharan, R., Ideker, T.: Modeling cellular machinery through biological network comparison. Nat. Biotechnol.\u00a024, 427\u2013433 (2006)","journal-title":"Nat. Biotechnol."},{"issue":"1","key":"6_CR16","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1038\/ng881","volume":"31","author":"S. Shen-Orr","year":"2002","unstructured":"Shen-Orr, S., Milo, R., Mangan, S., Alon, U.: Network motifs in the transcriptional regulation network of escherichia coli. Nat. Genet.\u00a031(1), 64\u201368 (2002)","journal-title":"Nat. Genet."},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comp.\u00a0(1), 146\u2013160 (1972)","DOI":"10.1137\/0201010"},{"issue":"4","key":"6_CR18","first-page":"347","volume":"3","author":"S. Wernicke","year":"2006","unstructured":"Wernicke, S.: Efficient detection of network motifs. IEEE ACM T. Comput. Bi.\u00a03(4), 347\u2013359 (2006)","journal-title":"IEEE ACM T. Comput. Bi."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69068-9_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:24:52Z","timestamp":1620015892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69068-9_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540690665","9783540690689"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69068-9_6","relation":{},"subject":[]}}