期刊名称：International Journal of Software Engineering and Its Applications
印刷版ISSN：1738-9984
出版年度：2014
卷号：8
期号：2
页码：343-358
DOI：10.14257/ijseia.2014.8.2.34
出版社：SERSC
摘要：Nowadays, graphs are used in many applications and the graph size is rapidly increasing. The shortest path discovery considering constraint conditions is very important. For example, when a road is temporarily not available, paths not including the invalid road are required. In this paper, we propose an efficient RDBMS based shortest path discovery method considering constraint conditions in a large graph. The proposed method finds the shortest path not containing the constraint path by avoiding expanding the paths including the given constraint path. We propose a novel approach that expands strategy by using the index table proposed by the FEM framework. We also propose an optimizing method for multiple constraint paths. We experimentally verify that our approaches can achieve high space and time efficiency in a large graph.
