Name
Abstract | ||
|---|---|---|
Parallel algorithms for recognizing and representing interval orders are proposed for different models of parallel random access machines (PRAM). The algorithms accept as input a transitively-closed directed graph with N nodes and M edges. They run in time O(log N ) with O( N + M ) processors and O( N + M ) space and in constant time with O( N 2 ) processors and O( N 2 ) space depending on the data structure and the PRAM model used. Optimal probabilistic algorithms for PRAM are also presented as well as algorithms for distributed-memory machines. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0304-3975(95)80011-5 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
interval representation,parallel interval order recognition | Journal | 143 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 0 |
PageRank | References | Authors |
0.34 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael A. Bender | 1 | 2144 | 138.24 |
| Michel Gastaldo | 2 | 10 | 4.08 |
| Michel Morvan | 3 | 211 | 33.41 |