Finding k disjoint paths (kDP) is a fundamental problem in graph analysis. For vertices s and t, paths from s to t are said to be disjoint if any two of them share no common vertex except s and t. In practice, disjoint paths are widely applied in network routing and transportation. In these scenarios, multiple kDP queries are often issued simultaneously, necessitating efficient batch processing. This motivates the study of batch kDP query processing (batch-k DP). A straightforward approach to batch-k DP extends batch simple-path enumeration with disjointness checks. But this suffers from factorial computational complexity. An alternative approach leverages single-query algorithms that avoid this by replacing the graph with a converted version. However, handling each query independently misses opportunities for shared computation. To overcome these limitations, we propose ShareDP, an algorithm for batch-k DP that shares the computation and storage across kDPs. ShareDP merges converted graphs into a shared structure, then shares the traversals and operations from different queries within this structure. Extensive experiments on 12 real-world datasets confirm the superiority of ShareDP over comparative approaches.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

ShareDP: Finding k Disjoint Paths for Multiple Vertex Pairs

  • Zhiqiu Yuan,
  • Youhuan Li,
  • Lei Zou,
  • Linglin Yang

摘要

Finding k disjoint paths (kDP) is a fundamental problem in graph analysis. For vertices s and t, paths from s to t are said to be disjoint if any two of them share no common vertex except s and t. In practice, disjoint paths are widely applied in network routing and transportation. In these scenarios, multiple kDP queries are often issued simultaneously, necessitating efficient batch processing. This motivates the study of batch kDP query processing (batch-k DP). A straightforward approach to batch-k DP extends batch simple-path enumeration with disjointness checks. But this suffers from factorial computational complexity. An alternative approach leverages single-query algorithms that avoid this by replacing the graph with a converted version. However, handling each query independently misses opportunities for shared computation. To overcome these limitations, we propose ShareDP, an algorithm for batch-k DP that shares the computation and storage across kDPs. ShareDP merges converted graphs into a shared structure, then shares the traversals and operations from different queries within this structure. Extensive experiments on 12 real-world datasets confirm the superiority of ShareDP over comparative approaches.