
doi: 10.3390/a7020243
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̧sieniec 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.
Output-sensitive algorithm, clique, time complexity, Industrial engineering. Management engineering, Clique, Analysis of algorithms and problem complexity, subgraph listing, subgraph isomorphism, T55.4-60.8, output-sensitive algorithm, Subgraph isomorphism, Graph algorithms (graph-theoretic aspects), Triangle, subgraph; subgraph isomorphism; subgraph listing; clique; triangle; output-sensitive algorithm; time complexity, Computer Sciences, triangle, QA75.5-76.95, Subgraph listing, Subgraph, Datavetenskap (datalogi), Time complexity, Electronic computers. Computer science, subgraph
Output-sensitive algorithm, clique, time complexity, Industrial engineering. Management engineering, Clique, Analysis of algorithms and problem complexity, subgraph listing, subgraph isomorphism, T55.4-60.8, output-sensitive algorithm, Subgraph isomorphism, Graph algorithms (graph-theoretic aspects), Triangle, subgraph; subgraph isomorphism; subgraph listing; clique; triangle; output-sensitive algorithm; time complexity, Computer Sciences, triangle, QA75.5-76.95, Subgraph listing, Subgraph, Datavetenskap (datalogi), Time complexity, Electronic computers. Computer science, subgraph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
