For Full-Text 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.
Frontier-Based Search for Enumerating All Constrained Subgraphs with Compressed Representation
Jun KAWAHARA Takeru INOUE Hiroaki IWASHITA Shin-ichi MINATO
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2017/09/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
zero-suppressed binary decision diagram, froniter-based search, enumeration algorithm, subgraph,
Full Text: PDF(1.3MB)>>
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 frontier-based search, which generalizes these specific algorithms without losing their efficiency. Our frontier-based search will be used to resolve various practical problems that include constrained subgraph enumeration.