{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:25:14Z","timestamp":1773271514381,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540734192","type":"print"},{"value":"9783540734208","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_31","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"340-351","source":"Crossref","is-referenced-by-count":30,"title":["Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Fertin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Hermelin","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":"31_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamson, K.R., Fellows, M.R.: Finite automata, bounded treewidth, and well-quasiordering. In: Robertson, N., Seymoued, P. (eds.), Graph Structure Theory, pp. 539\u2013564 (1993)","DOI":"10.1090\/conm\/147\/01199"},{"issue":"4","key":"31_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. Journal of the ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"Journal of the ACM"},{"issue":"1","key":"31_CR3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability. A survey. BIT Numerical Mathematics\u00a025(1), 2\u201323 (1985)","journal-title":"BIT Numerical Mathematics"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics\u00a023, 11\u201324 (1989)","journal-title":"Discrete Applied Mathematics"},{"key":"31_CR5","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica\u00a011, 1\u201323 (1993)","journal-title":"Acta Cybernetica"},{"key":"31_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/3-540-60084-1_65","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Fluiter, L.E.: Intervalizing k-colored graphs. In: F\u00fcl\u00f6p, Z., Gecseg, F. (eds.) Automata, Languages and Programming. LNCS, vol.\u00a0944, pp. 87\u201398. Springer, Heidelberg (1995)"},{"key":"31_CR7","unstructured":"Bodlaender, H.L., Fellows, M.R., Langston, M.A., Ragan, M.A., Rosamond, F.A., Weyer, M.: Kernelization for convex recoloring. In: Proceedings of the 2nd workshop on Algorithms and Complexity in Durham (ACiD), pp. 23\u201335 (2006)"},{"key":"31_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/3-540-55719-9_80","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1992","unstructured":"Bodlaender, H.L., Fellows, M.R., Warnow, T.: Two strikes against perfect phylogeny. In: Kuich, W. (ed.) Automata, Languages and Programming. LNCS, vol.\u00a0623, pp. 273\u2013283. Springer, Heidelberg (1992)"},{"key":"31_CR9","unstructured":"Chor, B., Fellows, M.R., Ragan, M.A., Rosamond, F.A., Snir, S.: Connected coloring completion for general graphs: Algorithms and complexity \u2013 Manuscript (2007)"},{"issue":"4","key":"31_CR10","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1137\/0608044","volume":"8","author":"D.G. Corneil","year":"1987","unstructured":"Corneil, D.G., Keil, J.M.: A dynamic programming approach to the dominating set problem on k-trees. SIAM Journal on Algebraic and Discrete Methods\u00a08(4), 535\u2013543 (1987)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"issue":"3","key":"31_CR11","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1093\/bib\/4.3.246","volume":"4","author":"Y. Deville","year":"2003","unstructured":"Deville, Y., Gilbert, D., Helden, J.V., Wodak, S.J.: An overview of data models for the analysis of biochemical pathways. Briefings in Bioinformatics\u00a04(3), 246\u2013259 (2003)","journal-title":"Briefings in Bioinformatics"},{"key":"31_CR12","doi-asserted-by":"crossref","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":"31_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-57273-2_52","volume-title":"Algorithms - ESA \u201993","author":"M.R. Fellows","year":"1993","unstructured":"Fellows, M.R., Hallett, M.T., Wareham, H.T.: DNA physical mapping: Three ways difficult. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol.\u00a0726, pp. 157\u2013168. Springer, Heidelberg (1993)"},{"key":"31_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1006\/aama.1994.1009","volume":"15","author":"M. Golumbic","year":"1994","unstructured":"Golumbic, M., Kaplan, H., Shamir, R.: On the complexity of DNA physical mapping. Advances in Applied Mathematics\u00a015, 251\u2013261 (1994)","journal-title":"Advances in Applied Mathematics"},{"issue":"2","key":"31_CR16","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1089\/cmb.2006.13.133","volume":"13","author":"T. Ideker","year":"2006","unstructured":"Ideker, T., Karp, R.M., Scott, J., Sharan, R.: Efficient algorithms for detecting signaling pathways in protein interaction networks. Journal of Computational Biology\u00a013(2), 133\u2013144 (2006)","journal-title":"Journal of Computational Biology"},{"issue":"20","key":"31_CR17","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. Proceedings of the National Academy of Sciences of the United States of America\u00a0100(20), 11394\u201311399 (2003)","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"issue":"4","key":"31_CR18","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"},{"issue":"2","key":"31_CR19","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0895480192229273","volume":"7","author":"F.R. McMorris","year":"1994","unstructured":"McMorris, F.R., Warnow, T.J., Wimer, T.: Triangulating vertex-colored graphs. SIAM Journal on Discrete Mathematics\u00a07(2), 296\u2013306 (1994)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"31_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/11534273_20","volume-title":"Algorithms and Data Structures","author":"S. Moran","year":"2005","unstructured":"Moran, S., Snir, S.: Convex recolorings of strings and trees: Definitions, hardness results and algorithms. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 218\u2013232. Springer, Heidelberg (2005)"},{"key":"31_CR21","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/100216.100244","volume-title":"STOC","author":"J. Naor","year":"1990","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. In: STOC. Proceedings of the 25th annual ACM Symposium on Theory Of Computing, pp. 213\u2013223. ACM Press, New York (1990)"},{"key":"31_CR22","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. SIAM Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"SIAM Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:11:06Z","timestamp":1619518266000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}