Computer Science – Data Structures and Algorithms
Scientific paper
2007-09-08
In Proceeding of 13th International Conference on Database Systems for Advanced Applications, 2008
Computer Science
Data Structures and Algorithms
15 pages, 11 figures, submitted to DASFAA 2008
Scientific paper
10.1007/978-3-540-78568-2
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 subgraph 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 subgraph homeomorphism determination (ndSHD) algorithms have been available. In this paper, we propose two computationally efficient ndSHD algorithms based on state spaces searching with backtracking, which employ many heuristics to prune the search spaces. Experimental results on synthetic data sets show that the proposed algorithms are efficient, require relative little time in most of the testing cases, can scale to large or dense graphs, and can accommodate to more complex fuzzy matching cases.
He Zhengying
Wang Wei
Wu Wentao
Xiao Yanghua
No associations
LandOfFree
Efficient Algorithms for Node Disjoint Subgraph Homeomorphism Determination does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient Algorithms for Node Disjoint Subgraph Homeomorphism Determination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Algorithms for Node Disjoint Subgraph Homeomorphism Determination will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-44525