Parallel Algorithm for Shortest Pairs of Edge-Disjoint Paths
| Autor: | S. Banerjee, R.K. Ghosh, A.P.K. Reddy |
|---|---|
| Rok vydání: | 1996 |
| Předmět: |
Computer Networks and Communications
Computer science Parallel algorithm Directed graph Disjoint sets Floyd–Warshall algorithm Theoretical Computer Science Vertex (geometry) Combinatorics Artificial Intelligence Hardware and Architecture Johnson's algorithm Software MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Journal of Parallel and Distributed Computing. 33:165-171 |
| ISSN: | 0743-7315 |
| Popis: | LetG= (V,E) be a directed graph having a nonnegative cost associated with each edge. Lets?Vbe a special vertex called the source andW?Vbe a set of other vertices called sinks inG. In this paper, a parallel algorithm is proposed for finding a pair of edge-disjoint paths fromsto each possible sinkt?Wsuch that the sum of the costs of the two paths is minimized. This algorithm has processor and time complexities same as those needed to find shortest paths fromsto all sinkst?W, i.e.,n3/lognprocessors andO(log2n) time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect