TCS-TR-A-14-76Date: Tue Sep 30 20:00:08 2014 Title: Frontier-based Search for Enumerating All Constrained Subgraphs with Compressed Representation Authors: Jun Kawahara, Takeru Inoue, Hiroaki Iwashita and Shin-ichi Minato Contact:
Abstract. For the subgraph enumeration problem, there have been proposed very efficient algorithms whose time complexities are far less than the number of subgraphs. Although the number of subgraphs can increase exponentially with the graph size, they exploit compressed representations to maintain enumerated subgraphs compactly so as to reduce the time complexity. However, they are designed for enumerating a speci c type of subgraphs only, e.g., paths or trees. In this paper, we propose a novel algorithm framework, called frontier-based search, which generalizes these speci c algorithms without losing their efficiency. We believe that our frontier-based search will be used to resolve various practical problems that include complicated subgraph enumeration. ©Copyright 2014 Authors |