A NEW ALGORITHM FOR INDUCED SUBGRAPH ISOMORPHISM

被引：0

作者：

Al-Saidi, Nadia M. G. ^{[1
]}

Rajab, Nuha A. ^{[1
]}

Abdul-Rahman, Hayder N. ^{[1
]}

机构：

[1] Univ Technol Baghdad, Dept Appl Sci, Branch Appl Math, Baghdad, Iraq

来源：

UNIVERSITY POLITEHNICA OF BUCHAREST SCIENTIFIC BULLETIN-SERIES A-APPLIED MATHEMATICS AND PHYSICS | 2016年 / 78卷 / 01期

关键词：

graph isomorphism; induced subgraph; incidence matrix; time;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Many algorithms to solve subgraph isomorphism problems have been proposed and proven to be NP-hard, but they did not demonstrate promising results especially on the large and dense graphs. In this paper, a new algorithm for determining an induced subgraph isomorphism between pattern and target graphs is proposed. It is based on decomposition of a graph into components and refinements. The incident matrices are used to help in rearranging the vertices in a descending order and reducing the search efforts. The algorithm is analyzed from complexity point of view to demonstrate its effectiveness after applying it on several types of graphs.

引用

页码：171 / 180

页数：10

共 50 条

[31] A Subgraph Isomorphism Algorithm for Privacy Preserving in Dynamic Social Network
He, Jing
Guo, Mengjiao
2019 IEEE/WIC/ACM INTERNATIONAL CONFERENCE ON WEB INTELLIGENCE WORKSHOPS (WI 2019 COMPANION), 2019, : 140 - 141
[32] Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem
Malik, Josef
Suchy, Ondrej
Valla, Tomas
ANALYSIS OF EXPERIMENTAL ALGORITHMS, SEA2 2019, 2019, 11544 : 283 - 299
[33] On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
Abu-Khzam, Faisal N.
Bonnet, Edouard
Sikora, Florian
COMBINATORIAL ALGORITHMS, IWOCA 2014, 2015, 8986 : 1 - 12
[34] Temporal Subgraph Isomorphism
Redmond, Ursula
Cunningham, Padraig
2013 IEEE/ACM INTERNATIONAL CONFERENCE ON ADVANCES IN SOCIAL NETWORKS ANALYSIS AND MINING (ASONAM), 2013, : 1451 - 1452
[35] A Parallel Subgraph Isomorphism Algorithm on Multi-core Platform
Yuan Long
Tian Weixin
APPLIED SCIENCE, MATERIALS SCIENCE AND INFORMATION TECHNOLOGIES IN INDUSTRY, 2014, 513-517 : 483 - 486
[36] Between Subgraph Isomorphism and Maximum Common Subgraph
Hoffmann, Ruth
McCreesh, Ciaran
Reilly, Craig
THIRTY-FIRST AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2017, : 3907 - 3914
[37] A Genetic and Iterative Local Search Algorithm for solving Subgraph Isomorphism Problem
Farahani, Mina Mazraeh
Chaharsoughi, Seyed Kamal
2015 INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND OPERATIONS MANAGEMENT (IEOM), 2015,
[38] An algorithm using length-r paths to approximate subgraph isomorphism
DePiero, F
Krout, D
PATTERN RECOGNITION LETTERS, 2003, 24 (1-3) : 33 - 46
[39] Logical complexity of induced subgraph isomorphism for certain families of graphs
Zhukovskii, M. E.
Kudryavtsev, E. D.
Makarov, M. V.
Shlychkova, A. S.
SBORNIK MATHEMATICS, 2021, 212 (04) : 517 - 530
[40] Induced Subgraph Isomorphism on proper interval and bipartite permutation graphs
Heggernes, Pinar
van 't Hof, Pim
Meister, Daniel
Villanger, Yngve
THEORETICAL COMPUTER SCIENCE, 2015, 562 : 252 - 269

← 1 2 3 4 5 →