{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1736617","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1736617","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q1736617","kernelVersion":"v1","immutable":true,"modified":"2026-03-31T05:06:08Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q1736617","name":"Efficient algorithms for subgraph listing","headline":"Efficient algorithms for subgraph listing","description":"scientific article; zbMATH DE number 7042205","url":"https://portal.mardi4nfdi.de/entity/Q1736617","datePublished":"2019-03-26","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q300257"},{"@id":"https://portal.mardi4nfdi.de/entity/Q293198"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q82263"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.3390/A7020243","url":"https://doi.org/10.3390/A7020243"},"sameAs":["https://doi.org/10.3390/A7020243"],"comment":"Summary: 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 \\textit{N. Chiba} and \\textit{T. Nishizeki} [SIAM J. Comput. 14, 210--223 (1985; Zbl 0572.68053)] 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 \\textit{L. Gąsieniec} et al. [Inf. Process. Lett. 109, No. 4, 242--247 (2009; Zbl 1190.65073)] 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.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q4198056"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3690237"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4167596"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3684121"},{"@id":"https://portal.mardi4nfdi.de/entity/Q976085"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3688439"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5710065"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5415522"},{"@id":"https://portal.mardi4nfdi.de/entity/Q915378"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3619797"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2842169"}]},"provenance":{"prov:generatedAtTime":"2026-03-31T05:06:08Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}