袁知秋关于多点对独立路径搜索问题的论文《ShareDP: Finding k Disjoint Paths for Multiple Vertex Pairs》的论文被DASFAA25接收。

寻找k条不相交路径（kDP）是图分析中的一个基本问题。对于顶点s和t，如果从s到t的路径除了s和t之外没有共同的顶点，则称这些路径是不相交的。在实际应用中，不相交路径广泛应用于网络路由和交通规划等领域。在这些场景中，常常需要同时处理多个kDP查询，因此需要高效的批处理方法。这促使了批量kDP查询处理（batch-kDP）的研究。一种直接的方法是扩展批量简单路径枚举，并加入不相交性检查。然而，这种方法存在阶乘计算复杂度的问题。另一种方法是利用单查询算法，通过将图转换为另一种形式来避免这种复杂度。然而，独立处理每个查询会错过共享计算的机会。为了克服这些限制，我们提出了ShareDP，一种用于批量kDP的算法，它在不同的kDP查询之间共享计算和存储。ShareDP将转换后的图合并为一个共享结构，然后在该结构中共享来自不同查询的遍历和操作。在12个真实数据集上的大量实验证实了ShareDP相较于其他方法的优越性。