{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:27:47Z","timestamp":1760243267190,"version":"build-2065373602"},"reference-count":13,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2014,5,15]],"date-time":"2014-05-15T00:00:00Z","timestamp":1400112000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Subgraph isomorphism is a fundamental problem in graph theory. In this paper we focus on listing subgraphs isomorphic to a given pattern graph. First, we look at the algorithm due to Chiba and Nishizeki for listing complete subgraphs of fixed size, and show that it cannot be extended to general subgraphs of fixed size. Then, we consider the algorithm due to Ga\u0327sieniec et al. for finding multiple witnesses of a Boolean matrix product, and use it to design a new output-sensitive algorithm for listing all triangles in a graph. As a corollary, we obtain an output-sensitive algorithm for listing subgraphs and induced subgraphs isomorphic to an arbitrary fixed pattern graph.<\/jats:p>","DOI":"10.3390\/a7020243","type":"journal-article","created":{"date-parts":[[2014,5,15]],"date-time":"2014-05-15T11:05:15Z","timestamp":1400151915000},"page":"243-252","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Algorithms for Subgraph Listing"],"prefix":"10.3390","volume":"7","author":[{"given":"Niklas","family":"Zechner","sequence":"first","affiliation":[{"name":"Department of Computing Science, Umea University, 901 87 Umea, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Lund University, 221 00 Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,5,15]]},"reference":[{"key":"ref_1","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability\u2014A Guide to the Theory of NP-Completeness, Bell Laboratories."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/0214017","article-title":"Arboricity and subgraph listing algorithms","volume":"14","author":"Chiba","year":"1985","journal-title":"SIAM J. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1137\/0207033","article-title":"Finding a minimum circuit in a graph","volume":"7","author":"Itai","year":"1978","journal-title":"SIAM J. Comput."},{"key":"ref_4","unstructured":"Gibbons, A. (1985). Algorithmic Graph Theory, Cambridge University Press."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1016\/j.ipl.2008.10.012","article-title":"Faster multi-witnesses for Boolean matrix multiplication","volume":"109","author":"Kowaluk","year":"2009","journal-title":"Inf. Process. Lett."},{"key":"ref_6","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Poljak","year":"1985","journal-title":"Comment. Math. Univ. Carol."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Schank, T., and Wagner, D. (2005, January 10\u201313). Finding, counting and listing all triangles in large graphs, an experimental study. Proceedings of the 4th International Workshop, WEA 2005, Santorini Island, Greece.","DOI":"10.1007\/11427186_54"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V. (2012, January 19\u201322). Multiplying matrices faster than coppersmith-winograd. Proceedings of the 44th Symposium on Theory of Computing Conference (STOC 2012), New York, NY, USA.","DOI":"10.1145\/2213977.2214056"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix multiplication via arithmetic progressions","volume":"9","author":"Coppersmith","year":"1990","journal-title":"J. Symb. Comput."},{"key":"ref_10","unstructured":"Cormen, T., Leiserson, C., and Rivest, R. (1990). Introduction to Algorithms, MIT Press."},{"key":"ref_11","unstructured":"Dvorak, Z., and Tuma, V. (2013, January 12\u201314). A dynamic data structure for counting subgraphs in sparse graphs. Proceedings of the 13th International Symposium, WADS 2013, London, ON, Canada. Lecture Notes in Computer Science."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s10618-005-0003-9","article-title":"Finding frequent patterns in a large sparse graph","volume":"11","author":"Kuramochi","year":"2005","journal-title":"Data Min. Knowl. Discov."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Le Gall, F. (2012, January 20\u201323). Faster algorithms for rectangular matrix multiplication. Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), New Brunswick, NJ, USA.","DOI":"10.1109\/FOCS.2012.80"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/2\/243\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:11:27Z","timestamp":1760217087000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/2\/243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,15]]},"references-count":13,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2014,6]]}},"alternative-id":["a7020243"],"URL":"https:\/\/doi.org\/10.3390\/a7020243","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2014,5,15]]}}}