{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T15:25:44Z","timestamp":1774625144419,"version":"3.50.1"},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Patt. Recogn. Artif. Intell."],"published-print":{"date-parts":[[2015,11]]},"abstract":"<jats:p> The subgraph isomorphism problem is one of the most important problems for pattern recognition in graphs. Its applications are found in many different disciplines, including chemistry, medicine, and social network analysis. Because of the [Formula: see text]-completeness of the problem, the existing exact algorithms exhibit an exponential worst-case running time. In this paper, we propose several improvements to the well-known Ullmann's algorithm for the problem. The improvements lower the time consumption as well as the space requirements of the algorithm. We experimentally demonstrate the efficiency of our improvement by comparing it to another set of improvements called FocusSearch, as well as other state-of-the-art algorithms, namely VF2 and LAD. <\/jats:p>","DOI":"10.1142\/s0218001415500251","type":"journal-article","created":{"date-parts":[[2015,7,5]],"date-time":"2015-07-05T23:11:51Z","timestamp":1436137911000},"page":"1550025","source":"Crossref","is-referenced-by-count":17,"title":["Improvements to Ullmann's Algorithm for the Subgraph Isomorphism Problem"],"prefix":"10.1142","volume":"29","author":[{"given":"Uro\u0161","family":"\u010cibej","sequence":"first","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, Ve\u010dna pot 113, 1000, Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jurij","family":"Miheli\u010d","sequence":"additional","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, Ve\u010dna pot 113, 1000, Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2015,9,28]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1021\/ci200413e"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1137\/100789403"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1021\/ci00014a001"},{"key":"rf4","first-page":"509","volume":"2","author":"Batra S.","year":"2012","journal-title":"Int. J. Soft Comput. Eng."},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-S7-S13"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04126-1_7"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(02)00253-2"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001414500013"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33293-7_11"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(96)00046-1"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1109\/34.954601"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70324-8"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1109\/69.842269"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.10.005"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001415500111"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1142\/S021800141550010X"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.05.002"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1145\/1671970.1921702"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04921-1"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311908"}],"container-title":["International Journal of Pattern Recognition and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218001415500251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:59:59Z","timestamp":1565110799000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218001415500251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,28]]},"references-count":24,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2015,9,28]]},"published-print":{"date-parts":[[2015,11]]}},"alternative-id":["10.1142\/S0218001415500251"],"URL":"https:\/\/doi.org\/10.1142\/s0218001415500251","relation":{},"ISSN":["0218-0014","1793-6381"],"issn-type":[{"value":"0218-0014","type":"print"},{"value":"1793-6381","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,28]]}}}