无回路有向图的深度第一支撑树的快速并行算法

摘要

cqvip:Ghosh和Bhattacharjee在[1]中提出的无回路有向图的深度第一支撑树的并行算法是错误的。本文解决了一般无回路有向图的深度第一支撑树的快速并行算法。其时间复杂度及处理器复杂度分别为O(log^2n)及O(n^3/log n)。