Efficient Algorithms for Node Disjoint Subgraph Homeomorphism Determination

Simple item page
dc.creatorXiao, Yanghua
dc.creatorWu, Wentao
dc.creatorWang, Wei
dc.creatorHe, Zhengying
dc.date2007-09-08
dc.date.accessioned2026-07-07T10:08:19Z
dc.date.available2026-07-07T10:08:19Z
dc.descriptionRecently, 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.
dc.description15 pages, 11 figures, submitted to DASFAA 2008
dc.identifierhttps://arxiv.org/abs/0709.1227
dc.identifierhttp://arxiv.org/abs/0709.1227
dc.identifierIn Proceeding of 13th International Conference on Database Systems for Advanced Applications, 2008
dc.identifierdoi:10.1007/978-3-540-78568-2
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/170953
dc.subjectData Structures and Algorithms
dc.subjectDatabases
dc.subjectF.2.2; G.2.2
dc.titleEfficient Algorithms for Node Disjoint Subgraph Homeomorphism Determination
dc.typetext

Files

Collections

arXiv