
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

FrontierBased Search for Enumerating All Constrained Subgraphs with Compressed Representation
Jun KAWAHARA Takeru INOUE Hiroaki IWASHITA Shinichi MINATO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E100A
No.9
pp.17731784 Publication Date: 2017/09/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E100.A.1773
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: zerosuppressed binary decision diagram, froniterbased search, enumeration algorithm, subgraph,
Full Text: PDF>>
Summary:
For subgraph enumeration problems, very efficient algorithms have been proposed whose time complexities are far smaller than the number of subgraphs. Although the number of subgraphs can exponentially increase with the input graph size, these algorithms exploit compressed representations to output and maintain enumerated subgraphs compactly so as to reduce the time and space complexities. However, they are designed for enumerating only some specific types of subgraphs, e.g., paths or trees. In this paper, we propose an algorithm framework, called the frontierbased search, which generalizes these specific algorithms without losing their efficiency. Our frontierbased search will be used to resolve various practical problems that include constrained subgraph enumeration.

