Weight-Constrained Simple Path Enumeration in Weighted Graph

摘要

Path enumeration is a fundamental problem and has been extensively studied in the literature. Given two query vertices and a weight threshold, the problem aims to identify all simple paths with weight not exceeding the threshold. Existing studies on path enumeration include DFS-based solutions and join-based solutions, where the join-based solutions only work for unweighted graphs. In this paper, we are the first to propose a join-based framework for weighted graphs. By observing the characteristics of DFS, we design a series of novel data structures and operations based on the join-based framework. In this way, our final solution combines the advantages of both join and DFS. We conduct experiments on several real large graphs. For weighted graphs, our method is much more efficient than existing algorithms. For unweighted graphs, our method is still competitive compared with the state-of-the-art solution which only works for unweighted graphs.