Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008
Given a graph, G = (V, E), and sets S ⊂ V and Q ⊂ V, the maximal paths problem requires the computation of a maximal set of vertex disjoint paths in G that begin at vertices of S and end at vertices of Q. It is well known that this problem can be solved sequentially in time that is proportional to the number of edges in G. However, its parallel complexity is not known. This note shows that this problem is NC-reducible to that of computing a depth-first search forest in a suitable n-vertex graph. This result can also be extended to directed graphs. © 1992.
Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008
Arun Viswanathan, Nancy Feldman, et al.
IEEE Communications Magazine
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
B. Wagle
EJOR