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 条
  • [21] Parallel organization algorithm for graph matching and subgraph isomorphism detection
    Nakanishi, Y
    Uehara, K
    DISCOVERY SCIENCE, 1998, 1532 : 407 - 408
  • [22] A Parallel, Backjumping Subgraph Isomorphism Algorithm Using Supplemental Graphs
    McCreesh, Ciaran
    Prosser, Patrick
    PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2015, 2015, 9255 : 295 - 312
  • [23] A Virtual Network Mapping Algorithm based on Subgraph Isomorphism Detection
    Lischka, Jens
    Karl, Holger
    VISA 09, 2009, : 81 - 88
  • [24] ON THE FIRST-ORDER COMPLEXITY OF INDUCED SUBGRAPH ISOMORPHISM
    Verbitsky, Oleg
    Zhukovskii, Maksim
    LOGICAL METHODS IN COMPUTER SCIENCE, 2019, 15 (01) : 25:1 - 25:24
  • [25] Investigation of incremental hybrid genetic algorithm with subgraph isomorphism problem
    Choi, HyukGeun
    Kim, Jinhyun
    Yoon, Yourim
    Moon, Byung-Ro
    SWARM AND EVOLUTIONARY COMPUTATION, 2019, 49 : 75 - 86
  • [26] INDUCED SUBGRAPH ISOMORPHISM FOR COGRAPHS IS NP-COMPLETE
    DAMASCHKE, P
    LECTURE NOTES IN COMPUTER SCIENCE, 1991, 484 : 72 - 78
  • [27] SGSI - A Scalable GPU-Friendly Subgraph Isomorphism Algorithm
    Zeng, Li
    Zou, Lei
    Ozsu, M. Tamer
    IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2023, 35 (11) : 11899 - 11916
  • [28] Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism
    Shang, Haichuan
    Zhang, Ying
    Lin, Xuemin
    Yu, Jeffrey Xu
    PROCEEDINGS OF THE VLDB ENDOWMENT, 2008, 1 (01): : 364 - 375
  • [29] PathLAD plus : An Improved Exact Algorithm for Subgraph Isomorphism Problem
    Wang, Yiyuan
    Jin, Chenghou
    Cai, Shaowei
    Lin, Qingwei
    PROCEEDINGS OF THE THIRTY-SECOND INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2023, 2023, : 5639 - 5647
  • [30] Filtering for subgraph isomorphism
    Zampelli, Stephane
    Deville, Yves
    Solnon, Christine
    Sorlin, Sebastien
    Dupont, Pierre
    PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2007, 2007, 4741 : 728 - +
12345