Name
Abstract | ||
|---|---|---|
In this paper we present algorithms for solving some combinatorial problems on one-dimensional processor arrays in which data
flows in only one direction through the array. The problems we consider are: ranking the elements in a chain of sizen, rooting a spanning tree withn vertices, and computing biconnected components of a connected graph withn vertices. We show that each of these problems can be solved using arrays of sizen in which the data enters at the first cell and flows through the array in only one direction until it leaves the last cell
as output. We also show how the biconnectivity algorithm for the array yields a new sequential algorithm for computing biconnected
components which uses onlyO(n) locations of random access memory. |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1007/BF01840384 | Algorithmica |
Keywords | Field | DocType |
Parallel graph algorithm,Systolic array,Disjoint set union,Biconnected component,Chain ranking,Euler tour | Block graph,Discrete mathematics,Combinatorics,k-vertex-connected graph,Biconnected component,Biconnected graph,Theoretical computer science,Dataflow,Spanning tree,Connectivity,Sequential algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
5 | 2 | 0178-4617 |
Citations | PageRank | References |
1 | 0.37 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carla D. Savage | 1 | 349 | 60.16 |
| Matthias F. M. Stallmann | 2 | 166 | 19.38 |
| Jo Ellen Perry | 3 | 27 | 2.78 |