Menu
A disjoint multiple paths problem asks if there exist paths between a given set of vertices. Constraints are applied so that paths are not allowed to share vertices (vertex disjoint multiple paths) or share edges (edge disjoint multiple paths). The vertex disjoint multiple paths problem is one of the classic NP-complete problems presented by Karp [1]. The edge disjoint multiple paths problem is also NP-complete since it is easily transformed from the vertex disjoint multiple paths problem. Because of its importance in electronic circuit design, studies are done for restricted cases. The edge disjoint multiple paths problem remains NP-complete for acyclic graphs and planar graphs. Furthermore, the edge disjoint multiple paths problem remains NP-complete if the graph is limited to an undirected mesh.
In this paper, the edge disjoint multiple paths problem when constructed over a directed mesh is discussed. We found that the multiple paths problem remains NP-complete in this special case. Three polynomial time algorithms are presented in which the following restrictions are made: (i) disjoint paths with the same origin row, the same destination row, distinct origin columns, and distinct destination columns, (ii) disjoint paths with the same origin column, the same destination column, distinct origin rows, and distinct destination rows, and (iii) disjoint paths with the same origin row, distinct origin columns, and distinct destination rows.