{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:29Z","timestamp":1759638809425},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,9,6]],"date-time":"2014-09-06T00:00:00Z","timestamp":1409961600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,5]]},"DOI":"10.1007\/s00224-014-9564-6","type":"journal-article","created":{"date-parts":[[2014,9,5]],"date-time":"2014-09-05T07:45:29Z","timestamp":1409903129000},"page":"612-629","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Some Results on More Flexible Versions of Graph Motif"],"prefix":"10.1007","volume":"56","author":[{"given":"Romeo","family":"Rizzi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,6]]},"reference":[{"issue":"2","key":"9564_CR1","doi-asserted-by":"crossref","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. Struct. Biol. 13 (2), 193\u2013202 (2003)","journal-title":"Curr. Opin. Struct. Biol."},{"key":"9564_CR2","doi-asserted-by":"crossref","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.): Proceedings of the 5th International Symposium Parameterized and Exact Computation (IPEC), Lecture Notes in Computer Science, vol. 6478, pp. 14\u201325. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-17493-3_4"},{"key":"9564_CR3","doi-asserted-by":"crossref","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.): Proceedings of the 19th Annual Symposium Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, vol. 5029, pp. 31\u201343. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-69068-9_6"},{"key":"9564_CR4","unstructured":"Bj\u00f6rklund, A., Kaski, P., Kowalik, L.: Probably optimal graph motifs. In: Portier, N.,Wilke, T. (eds.): Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, vol. 20, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012)"},{"key":"9564_CR5","doi-asserted-by":"crossref","unstructured":"B\u00f6cker, S., Rasche, F., Steijger, T.: Annotating Fragmentation Patterns. In: Salzberg, S., Warnow, T. (eds.) Proceedings of the 9th International Workshop Algorithms in Bioinformatics (WABI), Lecture Notes in Computer Science, Vol. 5724, pp 13\u201324. Springer, Berlin Heidelberg New York (2009)","DOI":"10.1007\/978-3-642-04241-6_2"},{"issue":"3","key":"9564_CR6","doi-asserted-by":"crossref","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."},{"issue":"1","key":"9564_CR7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0012-365X(81)90138-2","volume":"37","author":"M Chein","year":"1981","unstructured":"Chein, M., Habib, M., Maurer, M.C.: Partitive hypergraphs. Discret. Math. 37 (1), 35\u201350 (1981)","journal-title":"Discret. Math."},{"issue":"5964","key":"9564_CR8","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1126\/science.1180823","volume":"327","author":"M Costanzo","year":"2010","unstructured":"Costanzo, M., Baryshnikova, A., Bellay, J., Kim, Y., Spear, E.D., Sevier, C.S., Ding, H., Koh, J.L.Y., Toufighi, K., Mostafavi, S., Prinz, J., St. Onge, R.P., VanderSluis, B., Makhnevych, T., Vizeacoumar, F.J., Alizadeh, S., Bahr, S., Brost, R.L., Chen, Y., Cokol, M., Deshpande, R., Li, Z., Lin, Z.Y., Liang, W., Marback, M., Paw, J., San Luis, B.J., Shuteriqi, E., Tong, A.H., van Dyk, N., Wallace, I.M., Whitney, J.A., Weirauch, M.T., Zhong, G., Zhu, H., Houry, W.A., Brudno, M., Ragibizadeh, S., Papp, B., P\u00e1l, C., Roth, F.P., Giaever, G., Nislow, C., Troyanskaya, O.G., Bussey, H., Bader, G.D., Gingras, A.C., Morris, Q.D., Kim, P.M., Kaiser, C.A., Myers, C.L., Andrews, B.J., Boone, C.: The genetic landscape of a cell. Sci. 327 (5964), 425\u2013431 (2010)","journal-title":"Sci."},{"issue":"2","key":"9564_CR9","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0603021","volume":"3","author":"WH Cunningham","year":"1982","unstructured":"Cunningham, W.H.: Decomposition of directed graphs. SIAM J. Algebraic and Discret. Methods 3 (2), 214\u2013228 (1982)","journal-title":"SIAM J. Algebraic and Discret. Methods"},{"issue":"2","key":"9564_CR10","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.2000.1090","volume":"36","author":"E Dahlhaus","year":"2000","unstructured":"Dahlhaus, E.: Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition. J. Algorithm 36 (2), 205\u2013240 (2000)","journal-title":"J. Algorithm"},{"issue":"7","key":"9564_CR11","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1093\/bioinformatics\/btp083","volume":"25","author":"G Del Mondo","year":"2009","unstructured":"Del Mondo, G., Eveillard, D., Rusu, I.: Homogeneous decomposition of protein interaction networks: refining the description of intra-modular interactions. Bioinformatics 25 (7), 926\u2013932 (2009)","journal-title":"Bioinformatics"},{"key":"9564_CR12","doi-asserted-by":"crossref","unstructured":"Dondi, R., Fertin, G., Vialette, S.: Complexity issues in vertex-colored graph pattern matching. J. Discr. Algo. 9(1), 82\u201399 (2011)","DOI":"10.1016\/j.jda.2010.09.002"},{"key":"9564_CR13","doi-asserted-by":"crossref","unstructured":"Dondi, R., Fertin, G., Vialette, S.: Finding Approximate and Constrained Motifs in Graphs. In: Giancarlo, R., Manzini, G. (eds.) Proceedings of the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, Vol. 6661, pp 388\u2013401. Springer, Berlin Heidelberg New York (2011)","DOI":"10.1007\/978-3-642-21458-5_33"},{"key":"9564_CR14","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"10","key":"9564_CR15","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1016\/S0168-9525(02)02763-4","volume":"18","author":"AM Edwards","year":"2002","unstructured":"Edwards, A.M., Kus, B., Jansen, R., Greenbaum, D., Greenblatt, J., Gerstein, M.: Bridging structural biology and genomics: assessing protein interaction data with known complexes. Trends Genet. 18 (10), 529\u2013536 (2002)","journal-title":"Trends Genet."},{"key":"9564_CR16","doi-asserted-by":"crossref","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., Jurdzinski, T., Tarlecki, A. (eds.) Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, Vol. 4596, pp 340\u2013351. Springer, Poland (2007)","DOI":"10.1007\/978-3-540-73420-8_31"},{"issue":"8","key":"9564_CR17","doi-asserted-by":"crossref","first-page":"R57","DOI":"10.1186\/gb-2004-5-8-r57","volume":"5","author":"J Gagneur","year":"2004","unstructured":"Gagneur, J., Krause, R., Bouwmeester, T., Casari, G.: Modular decomposition of protein-protein interaction networks. Genome Biol. 5 (8), R57 (2004)","journal-title":"Genome Biol."},{"issue":"4","key":"9564_CR18","doi-asserted-by":"crossref","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":"9564_CR19","doi-asserted-by":"crossref","unstructured":"Habib, M., Montgolfier, F.d., Paul, C.: A Simple Linear-TimeModular Decomposition Algorithm for Graphs, Using Order Extension. In: Hagerup, T., Katajainen, J. (eds.): Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), Lecture Notes in Computer Science, vol. 3111, pp. 187\u2013198. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-27810-8_17"},{"key":"9564_CR20","doi-asserted-by":"crossref","unstructured":"Khanna, S., Motwani, R., Sudan, M., Vazirani, U.: On syntactic versus computational views of approximability, In: Proceedings of the 35th Annual IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 819\u2013830 (1994)","DOI":"10.1109\/SFCS.1994.365712"},{"issue":"22","key":"9564_CR21","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1016\/j.ipl.2012.08.008","volume":"112","author":"I Koutis","year":"2012","unstructured":"Koutis, I.: Constrained multilinear detection for faster functional motif discovery. Inf. Process. Lett. 112 (22), 889\u2013892 (2012)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9564_CR22","doi-asserted-by":"crossref","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. Bioinforma. (TCBB) 3 (4), 360\u2013368 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinforma. (TCBB)"},{"key":"9564_CR23","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms. Lecture Series in Mathematics and Its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Lecture Series in Mathematics and Its Applications. Oxford University Press, London (2006)"},{"issue":"5586","key":"9564_CR24","doi-asserted-by":"crossref","first-page":"1551","DOI":"10.1126\/science.1073374","volume":"297","author":"E Ravasz","year":"2002","unstructured":"Ravasz, E., Somera, A.L., Mongru, D.A., Oltvai, Z.N., Barabasi, A.L.: Hierarchical Organization of Modularity in Metabolic Networks. Sci. 297 (5586), 1551\u20131555 (2002)","journal-title":"Sci."},{"key":"9564_CR25","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, In: Proceedings of the 29th annual ACM Symposium on Theory of Computing (STOC), pp. 475\u2013484. ACM (1997)","DOI":"10.1145\/258533.258641"},{"issue":"2","key":"9564_CR26","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1038\/ng1165","volume":"34","author":"E Segal","year":"2003","unstructured":"Segal, E., Shapira, M., Regev, A., Pe\u2019er, D., Botstein, D., Koller, D., Friedman, N.: Module networks: identifying regulatory modules and their condition-specific regulators from gene expression data. Nat. Genet. 34 (2), 166\u2013176 (2003)","journal-title":"Nat. Genet."},{"issue":"4","key":"9564_CR27","doi-asserted-by":"crossref","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. 24 (4), 427\u2013433 (2006)","journal-title":"Nat. Biotechnol."},{"key":"9564_CR28","unstructured":"Sikora, F.: Aspects algorithmiques de la comparaison d\u2019\u00e9l\u00e9ments biologiques. Ph.D. thesis, Universit\u00e9 Paris-Est. (in French) (2011)"},{"issue":"1","key":"9564_CR29","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory Comput. 3 (1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9564-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9564-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9564-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T17:54:53Z","timestamp":1565805293000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9564-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,6]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["9564"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9564-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,6]]}}}