Title | ||
---|---|---|
A model classifying algorithms as inherently sequential with applications to graph searching |
Abstract | ||
---|---|---|
A model is proposed that can be used to classify algorithms as inherently sequential.The model captures the internal computations of algorithms. Previous work in complexitytheory has focused on the solutions algorithms compute. Direct comparison ofalgorithms within the framework of the model is possible. The model is useful for identifyinghard to parallelize constructs that should be avoided by parallel programmers.The model's utility is demonstrated via applications to graph searching. A ... |
Year | DOI | Venue |
---|---|---|
1992 | 10.1016/0890-5401(92)90033-C | Inf. Comput. |
Field | DocType | Volume |
Graph,Combinatorics,Search algorithm,Queue,Breadth-first search,Algorithm,Contrast (statistics),Mathematics,Computation | Journal | 97 |
Issue | ISSN | Citations |
2 | Information and Computation | 13 |
PageRank | References | Authors |
0.96 | 15 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Raymond Greenlaw | 1 | 142 | 18.56 |