[1] |
Ajtai, M.; Komlós, J.; Szemerédi, E., An \(O(n\) log \(n)\) sorting network, Combinatorica, 3, 1, 1-19 (1983) · Zbl 0523.68048 |
[2] |
Awerbuch, B.; Shiloach, Y., New connectivity and MSF algorithms for Ultracomputer and PRAM, (Proc. 1983 Internat. Conf. on Parallel Processing (1983)) · Zbl 0643.94044 |
[3] |
Atallah, M., Parallel strong orientation of an undirected graph, Inform. Process. Lett., 18, 37-39 (1984) · Zbl 0532.68065 |
[4] |
Chin, F. Y.; Lam, J.; Chen, I., Optimal parallel algorithms for the connected component problems, (Proc. 1981 Internat. Conf. on Parallel Processing (1981)), 170-175 |
[5] |
Reif, J. H., Depth-first search is inherently sequential, Inform. Process. Lett., 20, 5, 229-234 (1985), (this issue) · Zbl 0572.68051 |
[6] |
Reif, J. H.; Valiant, L. G., A logarithmic time sort for linear size network, (Proc. 15th ACM Symp. on Theory of Computing (1983)), 10-16 |
[7] |
Shiloach, Y.; Vishkin, U., An O(log \(n)\) parallel connectivity algorithm, J. Algorithms, 3, 57-67 (1982) · Zbl 0494.68070 |
[8] |
Tarjan, R. E., Finding dominators in directed graphs, SIAM J. Comput., 3, 62-89 (1974) · Zbl 0296.68030 |
[9] |
Tarjan, R. E.; Vishkin, U., An efficient parallel biconnectivity algorithm, (Tech. Rept. 69 (1983), Dept. of Computer Science, Courant Institute, New York Univ) · Zbl 0575.68066 |
[10] |
also: SIAM J. Comput., to appear.; also: SIAM J. Comput., to appear. |
[11] |
Tarjan, R. E.; Vishkin, U., Finding biconnected components and computing tree functions in logarithmic parallel time, (Proc. 25th IEEE Symp. on Foundations of Computer Science (1984)), 12-20 |
[12] |
Vishkin, U., An optimal parallel connectivity algorithm, Discrete Appl. Math., 9, 2, 197-207 (1984) · Zbl 0546.68044 |
[13] |
Vishkin, U., Synchronous parallel computation—a survey, (Tech. Rept. 71 (1983), Dept. of Computer Science, Courant Institute, New York Univ) |
[14] |
Vishkin, U., Randomized speed-ups in parallel computation, (Proc. 16th ACM Symp. on Theory of Computing (1984)), 230-239 |