Frontier-Based Search for Enumerating All Constrained Subgraphs with Compressed Representation

Jun KAWAHARA  Takeru INOUE  Hiroaki IWASHITA  Shin-ichi MINATO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A   No.9   pp.1773-1784
Publication Date: 2017/09/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
zero-suppressed binary decision diagram,  froniter-based search,  enumeration algorithm,  subgraph,  

Full Text: PDF(1.3MB)
>>Buy this Article


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 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.