Publication
Information Processing Letters
Paper

Parallel complexity of computing a maximal set of disjoint paths

View publication

Abstract

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.

Date

06 Mar 1992

Publication

Information Processing Letters

Authors

Topics

Share