Frontier-Based Search for Enumerating All Constrained Subgraphs with Compressed Representation
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.9 pp.1773-1784
- Publication Date
- 2017/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E100.A.1773
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Jun KAWAHARA
Nara Institute of Science and Technology
Takeru INOUE
NTT Corporation
Hiroaki IWASHITA
Fujitsu Laboratories Limited
Shin-ichi MINATO
Hokkaido University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Jun KAWAHARA, Takeru INOUE, Hiroaki IWASHITA, Shin-ichi MINATO, "Frontier-Based Search for Enumerating All Constrained Subgraphs with Compressed Representation" in IEICE TRANSACTIONS on Fundamentals,
vol. E100-A, no. 9, pp. 1773-1784, September 2017, doi: 10.1587/transfun.E100.A.1773.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.1773/_p
Copy
@ARTICLE{e100-a_9_1773,
author={Jun KAWAHARA, Takeru INOUE, Hiroaki IWASHITA, Shin-ichi MINATO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Frontier-Based Search for Enumerating All Constrained Subgraphs with Compressed Representation},
year={2017},
volume={E100-A},
number={9},
pages={1773-1784},
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.},
keywords={},
doi={10.1587/transfun.E100.A.1773},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Frontier-Based Search for Enumerating All Constrained Subgraphs with Compressed Representation
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1773
EP - 1784
AU - Jun KAWAHARA
AU - Takeru INOUE
AU - Hiroaki IWASHITA
AU - Shin-ichi MINATO
PY - 2017
DO - 10.1587/transfun.E100.A.1773
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2017
AB - 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.
ER -
English
