Name
Title | ||
|---|---|---|
Frontier-Based Search For Enumerating All Constrained Subgraphs With Compressed Representation |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1587/transfun.E100.A.1773 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES |
Keywords | Field | DocType |
zero-suppressed binary decision diagram, froniter-based search, enumeration algorithm, subgraph | Graph,Discrete mathematics,Enumeration,Exploit,Theoretical computer science,Time complexity,Enumeration algorithm,Frontier,Mathematics | Journal |
Volume | Issue | ISSN |
E100A | 9 | 1745-1337 |
Citations | PageRank | References |
5 | 0.56 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jun Kawahara | 1 | 34 | 8.82 |
| Takeru Inoue | 2 | 176 | 19.11 |
| Hiroaki Iwashita | 3 | 89 | 9.62 |
| Shin-ichi Minato | 4 | 725 | 84.72 |