×
Vishkin, Uzi

On efficient parallel strong orientation. (English) Zbl 0603.68067

Inf. Process. Lett. 20, 235-240 (1985).

Cited in 15 Documents

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C40 Connectivity

Keywords:

bridgeless graphs; graph algorithm; parallel algorithm; strongly connected component; parallel random access machines; PRAM
Cite Review PDF
Full Text: DOI

References:

[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.