Detecting Non-subgraphs Efficiently by Comparing Eigenvalues of Decomposed Graphs
Summary :
The problem of deciding whether a graph contains another graph appears in various applications. For solving this problem efficiently, we developed a numerical method to detect non-subgraphs, graphs which are not subgraphs of other graphs, by comparing eigenvalues of graphs. In this paper, we propose a method to make the detection more efficient by comparing of eigenvalues of graphs decomposed according to labels of the vertices and the edges. The new approach not only reduces the cost of computing eigenvalues but also increases the possibility of detecting non-subgraphs. The experimental evaluation shows the effectiveness of the proposed method.
- Publication
- IEICE TRANSACTIONS on Information Vol.E95-D No.11 pp.2724-2727
- Publication Date
- 2012/11/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E95.D.2724
- Type of Manuscript
- LETTER
- Category
- Data Engineering, Web Information Systems
Authors
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
Kaoru KATAYAMA, Yosuke AMAGASA, Hideki NAGAYA, "Detecting Non-subgraphs Efficiently by Comparing Eigenvalues of Decomposed Graphs" in IEICE TRANSACTIONS on Information,
vol. E95-D, no. 11, pp. 2724-2727, November 2012, doi: 10.1587/transinf.E95.D.2724.
Abstract: The problem of deciding whether a graph contains another graph appears in various applications. For solving this problem efficiently, we developed a numerical method to detect non-subgraphs, graphs which are not subgraphs of other graphs, by comparing eigenvalues of graphs. In this paper, we propose a method to make the detection more efficient by comparing of eigenvalues of graphs decomposed according to labels of the vertices and the edges. The new approach not only reduces the cost of computing eigenvalues but also increases the possibility of detecting non-subgraphs. The experimental evaluation shows the effectiveness of the proposed method.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E95.D.2724/_p
Copy
@ARTICLE{e95-d_11_2724,
author={Kaoru KATAYAMA, Yosuke AMAGASA, Hideki NAGAYA, },
journal={IEICE TRANSACTIONS on Information},
title={Detecting Non-subgraphs Efficiently by Comparing Eigenvalues of Decomposed Graphs},
year={2012},
volume={E95-D},
number={11},
pages={2724-2727},
abstract={The problem of deciding whether a graph contains another graph appears in various applications. For solving this problem efficiently, we developed a numerical method to detect non-subgraphs, graphs which are not subgraphs of other graphs, by comparing eigenvalues of graphs. In this paper, we propose a method to make the detection more efficient by comparing of eigenvalues of graphs decomposed according to labels of the vertices and the edges. The new approach not only reduces the cost of computing eigenvalues but also increases the possibility of detecting non-subgraphs. The experimental evaluation shows the effectiveness of the proposed method.},
keywords={},
doi={10.1587/transinf.E95.D.2724},
ISSN={1745-1361},
month={November},}
Copy
TY - JOUR
TI - Detecting Non-subgraphs Efficiently by Comparing Eigenvalues of Decomposed Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 2724
EP - 2727
AU - Kaoru KATAYAMA
AU - Yosuke AMAGASA
AU - Hideki NAGAYA
PY - 2012
DO - 10.1587/transinf.E95.D.2724
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E95-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2012
AB - The problem of deciding whether a graph contains another graph appears in various applications. For solving this problem efficiently, we developed a numerical method to detect non-subgraphs, graphs which are not subgraphs of other graphs, by comparing eigenvalues of graphs. In this paper, we propose a method to make the detection more efficient by comparing of eigenvalues of graphs decomposed according to labels of the vertices and the edges. The new approach not only reduces the cost of computing eigenvalues but also increases the possibility of detecting non-subgraphs. The experimental evaluation shows the effectiveness of the proposed method.
ER -
English
