Algorithms | |
Efficient Algorithms for Subgraph Listing | |
Niklas Zechner1  | |
[1] Department of Computing Science, Umea University, 901 87 Umea, Sweden | |
关键词: subgraph; subgraph isomorphism; subgraph listing; clique; triangle; output-sensitive algorithm; time complexity; | |
DOI : 10.3390/a7020243 | |
来源: mdpi | |
【 摘 要 】
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 Gąsieniec
【 授权许可】
CC BY
© 2014 by the authors; licensee MDPI, Basel, Switzerland.
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO202003190025974ZK.pdf | 198KB | download |