{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T07:09:51Z","timestamp":1791270591232,"version":"4.1.0"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size $s$ and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.<\/jats:p>","DOI":"10.1137\/140978211","type":"journal-article","created":{"date-parts":[[2015,8,4]],"date-time":"2015-08-04T13:03:40Z","timestamp":1438693420000},"page":"1322-1339","source":"Crossref","is-referenced-by-count":16,"title":["Detecting and Counting Small Pattern Graphs"],"prefix":"10.1137","volume":"29","author":[{"given":"Peter","family":"Floderus","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Miros\u0141aw","family":"Kowaluk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eva-Marta","family":"Lundell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,8,4]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/0214065"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/070695149"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.033"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"atypb8","first-page":"37","author":"Floderus P.","year":"2012","journal-title":"New York"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.10.001"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"B. Gelbord,\n                      Graphical techniques in intrusion detection systems\n                      , in Proceedings of the 15th International Conference on Information Networks, 2001, pp. 253-258.","DOI":"10.1109\/ICOIN.2001.905436"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.01.024"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00047-8"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/110859798"},{"key":"atypb14","first-page":"653","author":"Koutis I.","year":"2009","journal-title":"New York"},{"key":"atypb15","first-page":"514","author":"Le Gall F.","year":"2012","journal-title":"Proceedings of FOCS"},{"key":"atypb16","first-page":"415","volume":"26","author":"Nes\u0306etr\u0306il J.","year":"1985","journal-title":"Comment. Math. Univ. Carolin."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90143-3"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"T. Schank and D. Wagner,\n                      Finding, counting and listing all triangles in large graphs, an experimental study\n                      , in Experimental and Efficient Algorithms, Lecture Notes in Comput. Sci. 3503, 2005, Springer, New York, pp. 606-609.","DOI":"10.1007\/11427186_54"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/1640457.1640458"},{"key":"atypb21","first-page":"1671","author":"Vassilevska Williams V.","year":"2015","journal-title":"Proceedings of SODA"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"atypb23","unstructured":"V. Vassilevska,\n                      Efficient Algorithms for Path Problems in Weighted Graphs\n                      , Ph.D. thesis, Carnegie Mellon University, Pittsburgh, 2008."},{"key":"atypb24","first-page":"455","author":"Vassilevska V.","year":"2009","journal-title":"Proceedings of STOC"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140978211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:17:47Z","timestamp":1787318267000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140978211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140978211"],"URL":"https:\/\/doi.org\/10.1137\/140978211","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}