Data Management

Efficient Algorithms for Node Disjoint Subgraph Homeomorphism Determination

Download Now Date Added: Sep 2007
Format: PDF

Recently, great efforts have been dedicated to researches on the management of large scale graph based data such as WWW, social networks, biological networks. In the study of graph based data management, node disjoint sub-graph homeomorphism relation between graphs is more suitable than (sub) graph isomorphism in many cases, especially in those cases that node skipping and node mismatching are allowed. However, no efficient node disjoint Sub-graph Homeomorphism Determination (ndSHD) algorithms have been available. In this paper, the authors propose two computationally efficient ndSHD algorithms based on state spaces searching with backtracking, which employ many heuristics to prune the search spaces.