Xinyi Su, Guangyu He, et al.
Dianli Xitong Zidonghua/Automation of Electric Power Systems
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.
Xinyi Su, Guangyu He, et al.
Dianli Xitong Zidonghua/Automation of Electric Power Systems
Fan Zhang, Junwei Cao, et al.
IEEE TETC
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
Rajiv Ramaswami, Kumar N. Sivarajan
IEEE/ACM Transactions on Networking