{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:23:57Z","timestamp":1764689037443},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,3,4]],"date-time":"2015-03-04T00:00:00Z","timestamp":1425427200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00453-015-9981-1","type":"journal-article","created":{"date-parts":[[2015,3,3]],"date-time":"2015-03-03T13:46:11Z","timestamp":1425390371000},"page":"947-967","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Constrained Multilinear Detection and Generalized Graph Motifs"],"prefix":"10.1007","volume":"74","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petteri","family":"Kaski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u0141ukasz","family":"Kowalik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,3,4]]},"reference":[{"key":"9981_CR1","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: Proceedings of CPM\u201908. LNCS, vol. 5029, pp. 31\u201343 (2008)","DOI":"10.1007\/978-3-540-69068-9_6"},{"key":"9981_CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected hamiltonicity. In: Proceedings of the FOCS\u201910, pp. 173\u2013182 (2010)","DOI":"10.1109\/FOCS.2010.24"},{"key":"9981_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A.: Counting perfect matchings as fast as Ryser. In: Proceedings of the SODA\u201912, pp. 914\u2013921 (2012)","DOI":"10.1137\/1.9781611973099.73"},{"key":"9981_CR4","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings. CoRR. abs\/1007.1161 (2010)"},{"key":"9981_CR5","first-page":"20","volume-title":"STACS. LIPIcs","author":"A Bj\u00f6rklund","year":"2013","unstructured":"Bj\u00f6rklund, A., Kaski, P., Kowalik, L.: Probably optimal graph motifs. In: Portier, N., Wilke, T. (eds.) STACS. LIPIcs, vol. 20, pp. 20\u201331. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Wadern (2013)"},{"key":"9981_CR6","volume-title":"Algebraic Complexity Theory, Grundlehren der mathematischen Wissenschaften","author":"P B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory, Grundlehren der mathematischen Wissenschaften, vol. 315. Springer, New York (1997)"},{"key":"9981_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNF-SAT. In: IEEE Conference on Computational Complexity, pp. 74\u201384 (2012)","DOI":"10.1109\/CCC.2012.36"},{"key":"9981_CR8","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"RA DeMillo","year":"1978","unstructured":"DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Inf. Process. Lett. 7, 193\u2013195 (1978)","journal-title":"Inf. Process. Lett."},{"key":"9981_CR9","doi-asserted-by":"crossref","unstructured":"Dondi, R., Fertin, G., Vialette, S.: Maximum motif problem in vertex-colored graphs. In: Proceedings of the CPM\u201909. LNCS, vol. 5577, pp. 221\u2013235 (2009)","DOI":"10.1007\/978-3-642-02441-2_20"},{"key":"9981_CR10","doi-asserted-by":"crossref","unstructured":"Dondi, R., Fertin, G., Vialette, S.: Finding approximate and constrained motifs in graphs. In: Proceedings of the CPM\u201911. LNCS, vol. 6661, pp. 388\u2013401 (2011)","DOI":"10.1007\/978-3-642-21458-5_33"},{"key":"9981_CR11","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: Proceedings of the ICALP\u201907. LNCS, vol. 4596, pp. 340\u2013351 (2007)","DOI":"10.1007\/978-3-540-73420-8_31"},{"issue":"4","key":"9981_CR12","doi-asserted-by":"crossref","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":"9981_CR13","doi-asserted-by":"crossref","unstructured":"Guillemot, S., Sikora, F.: Finding and counting vertex-colored subtrees. In: Proceedings of the MFCS\u201910. LNCS, vol. 6281, pp. 405\u2013416 (2010)","DOI":"10.1007\/978-3-642-15155-2_36"},{"key":"9981_CR14","doi-asserted-by":"crossref","unstructured":"Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Proceedings of the ICALP\u201908. LNCS, vol. 5125, pp. 575\u2013586 (2008)","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"9981_CR15","unstructured":"Koutis, I.: The power of group algebras for constrained multilinear monomial detection. In: Dagstuhl meeting 10441 (2010)"},{"issue":"22","key":"9981_CR16","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."},{"key":"9981_CR17","doi-asserted-by":"crossref","unstructured":"Koutis, I., Williams, R.: Limits and applications of group algebras for parameterized problems. In: ICALP (1). LNCS, vol. 5555, pp. 653\u2013664 (2009)","DOI":"10.1007\/978-3-642-02927-1_54"},{"issue":"4","key":"9981_CR18","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. Bioinform. 3(4), 360\u2013368 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9981_CR19","doi-asserted-by":"crossref","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using M\u00f6bius inversion: improving on Steiner tree and related problems. In: Proceedings of the ICALP\u201909. LNCS, vol. 5555, pp. 713\u2013725 (2009)","DOI":"10.1007\/978-3-642-02927-1_59"},{"issue":"4","key":"9981_CR20","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"issue":"6","key":"9981_CR21","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length $$k$$ k in $$O^*(2^k)$$ O \u2217 ( 2 k ) time. Inf. Process. Lett. 109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9981_CR22","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation. LNCS, vol. 72, pp. 216\u2013226 (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9981-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9981-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9981-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,26]],"date-time":"2019-02-26T14:15:49Z","timestamp":1551190549000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9981-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,4]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9981"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9981-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2015,3,4]]}}}