{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T09:44:51Z","timestamp":1698313491992},"reference-count":20,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4120,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1995,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Although the general problem of subgraph isomorphism is NP\u2010complete, polynomial\u2010time algorithms exist for recognizing any fixed subgraph. However, certain subgraphs appear easier to recognize than others. In this paper, we present general algorithms for fixed\u2010subgraph isomorphism which improve or unify previous results. In particular, we present an O(n<jats:sup>f<\/jats:sup>m) algorithm for recognizing a fixed subgraph <jats:italic>H<\/jats:italic> with flower number <jats:italic>f<\/jats:italic> within a graph <jats:italic>G<\/jats:italic> with <jats:italic>n<\/jats:italic> vertices and <jats:italic>m<\/jats:italic> edges. Special cases of this algorithm match the best algorithms known for recognizing small paths, cycles, and cliques. Further, we improve previous results for recognizing <jats:italic>C<\/jats:italic><jats:sub>5<\/jats:sub> and small even cycles <jats:italic>C<\/jats:italic><jats:sub>2k<\/jats:sub>, <jats:italic>k<\/jats:italic> \u2265 3.<\/jats:p>","DOI":"10.1002\/net.3230250404","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T19:49:14Z","timestamp":1178999354000},"page":"183-191","source":"Crossref","is-referenced-by-count":6,"title":["Recognizing small subgraphs"],"prefix":"10.1002","volume":"25","author":[{"given":"Gopalakrishnan","family":"Sundaram","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steven S.","family":"Skiena","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51542-9_48"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90052-5"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1080\/00207168908803783"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214065"},{"key":"e_1_2_1_7_2","unstructured":"D.Eppstein Connectivity graph minors and subgraph multiplicity. Tech. Report 92\u201306 University of California Irvine (1992)."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02024498"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"M. R.FellowsandM.Langston On search decision and the efficiency of polynomial\u2010time algorithms.21st ACM Symposium on Theory of Computing(1989)514\u2013524.","DOI":"10.1145\/73007.73055"},{"key":"e_1_2_1_10_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_2_1_12_2","first-page":"239","article-title":"How to find long paths efficiently","volume":"25","author":"Monien B.","year":"1985","journal-title":"Ann. Disc. Math."},{"key":"e_1_2_1_13_2","unstructured":"S.Naher LEDA User Manual(1993)."},{"key":"e_1_2_1_14_2","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Nesetril J.","year":"1985","journal-title":"Comm. Math. Univ. Carol."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/322307.322309"},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"J.PlehnandB.Voigt Finding minimally weighted subgraphs.Workshop on Graph Theoretic Concepts in Computer Science(1990).","DOI":"10.1007\/3-540-53832-1_28"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90029-5"},{"key":"e_1_2_1_18_2","first-page":"249","article-title":"Finding cycles of a given length","volume":"27","author":"Richards D.","year":"1985","journal-title":"Ann. Discr. Math."},{"key":"e_1_2_1_19_2","unstructured":"N.RobertsonandP. D.Seymour Graph minors XVI. Wagner's conjecture. To appear."},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230250404","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230250404","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T18:36:49Z","timestamp":1698259009000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230250404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["10.1002\/net.3230250404"],"URL":"https:\/\/doi.org\/10.1002\/net.3230250404","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}