![]() IEEE, (2013)Ĭhondrogiannis, T., Bouros, P., Gamper, J., Leser, U., Blumenthal, D.B.: Finding k-dissimilar paths with minimum collective length. In 2013 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), pages 46–53. arXiv preprint arXiv:2010.08938, (2020)Ĭheng, Y., Li, J., Sterbenz, J.P.: Path geo-diversification: Design and analysis. In EDBT 2015-18th International Conference on Extending Database Technology, Proceedings, (2015)Ĭhen, X., Lai, L., Qin, L., Lin, X., Liu, B.: A framework to quantify approximate simulation on graph data. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems, pages 155–166, (2012)Ĭhang, L., Lin, X., Qin, L., Yu, J.X., Pei, J.: Efficiently computing top-k shortest path join. In SODA, pages 1884–1896, (2013)īorodin, A., Lee, H.C., Ye, H.C.: Max-sum diversification, monotone submodular functions and dynamic updates. European Journal of Operational Research 121(2), 232–246 (2000)īirmelé, E., Ferreira, R.A., Grossi, R., Marino, A., Pisanti, N., Rizzi, R., Sacomoto, G.: Optimal listing of cycles and st-paths in undirected graphs. Journal of Experimental Algorithmics (JEA) 18, 1–1 (2013)Īkgün, V., Erkut, E., Batta, R.: On finding dissimilar paths. The experiments show our proposed methods significantly improve the query time and scalability comparing with baselines.Ībraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Alternative routes in road networks. To further speed up the computation, hybrid lower bounds based on reverse shortest-path tree are also developed, namely SCB+. ![]() In this paper, we also study the hop-constrained path enumeration problem with diversity constraint and propose a block-oriented algorithm, namely SCB. It is also reported that the JOIN algorithm can further significantly enhance the query response time. On the practical side, our comprehensive experiments on 15 real-life networks demonstrate the superior performance of the BC-DFS algorithm compared to the state-of-the-art techniques. This time complexity is similar to the best known theoretical result for the polynomial delay algorithms of this problem. On the theoretical side, BC-DFS is a polynomial delay algorithm with O( km) time per output where m is the number of edges in the graph. Then, a join-oriented algorithm, namely JOIN, is designed to further enhance the query response time. We first propose a polynomial delay algorithm, namely BC-DFS, based on a barrier-based pruning technique. For this purpose, we study the problem of hop-constrained s- t simple path enumeration in this paper, which aims to list all simple paths from a source vertex s to a target vertex t with hop-constraint k. One of the fundamental tasks in graph analytics is to investigate the relations between two vertices (e.g., users, items, and entities) such as how a vertex A influences another vertex B, or to what extent A and B are similar to each other, based on the graph topology structure. Graph is a ubiquitous structure representing entities and their relationships applied in many areas such as social networks, web graphs, and biological networks.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |