More Web Proxy on the site http://driver.im/

research-article

Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests

Authors:

Uri ZwickAuthors Info & Claims

Journal of Algorithms, Volume 39, Issue 1

Pages 1 - 46

https://doi.org/10.1006/jagm.2000.1146

Published: 01 April 2001 Publication History

Abstract

We present the first randomized O(logn) time and O(m+n) work EREW PRAM algorithm for finding a spanning forest of an undirected graph G=(V,E) with n vertices and m edges. Our algorithm is optimal with respect to time, work, and space. As a consequence we get optimal randomized EREW PRAM algorithms for other basic connectivity problems such as finding a bipartite partition, finding bridges and biconnected components, finding Euler tours in Eulerian graphs, finding an ear decomposition, finding an open ear decomposition, finding a strong orientation, and finding an st-numbering.

References

[1]

B. Awerbuch, A. Israeli, Y. Shiloach, Finding Euler circuits in logarithmic parallel time, in: Advances in Computing Research, JAI Press, 1987, pp. 79-86.

[2]

R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, C. Rackoff, Random walks, universal sequences and the complexity of maze problems, 1979.

[3]

B. Awerbuch, Y. Shiloach, New connectivity and MSF algorithms for shuffle-exchange network and PRAM, IEEE Trans. Comput., 36 (1987) 1258-1263.

Digital Library

[4]

N. Alon, J.H. Spencer, Wiley, New York, 1992.

[5]

M.J. Atallah, U. Vishkin, Finding Euler tours in parallel, J. Comput. Syst. Sci., 29 (1984) 330-337.

Digital Library

[6]

G. Barnes, U. Feige, Short random walks on graphs, SIAM J. Discrete Mathematics, 9 (1996) 19-28.

Digital Library

[7]

R. Cole, P.N. Klein, R.E. Tarjan, Finding minimum spanning forests in logarithmic time and linear work using random sampling, 1996.

[8]

K.W. Chong, T.W. Lam, Finding connected components in O(lognloglogn) time on the EREW PRAM, J. Algorithms, 18 (1995) 378-402.

Digital Library

[9]

F.Y. Chin, J. Lam, I.N. Chen, Efficient parallel algorithms for some graph problems, Commun. ACM, 25 (1982) 659-665.

Digital Library

[10]

R. Cole, Parallel merge-sort, SIAM J. Comput., 17 (1988) 770-785.

Digital Library

[11]

R. Cole, U. Vishkin, Approximate parallel scheduling. Part II: Applications to logarithmic-time optimal graph algorithms, Inform. and Comput., 92 (1991) 1-47.

Digital Library

[12]

D. Fussell, V. Ramachandran, R. Thurimella, Finding triconnected components by local replacement, SIAM J. Comput., 22 (1993) 587-616.

Digital Library

[13]

H. Gazit, An optimal randomized parallel algorithm for finding connected components in a graph, SIAM J. Comput., 20 (1991) 1046-1067.

Digital Library

[14]

H.N. Gabow, J.L. Bentley, R.E. Tarjan, Scaling and related techniques for geometry problems, 1984.

[15]

M.T. Goodrich, S.R. Kosaraju, Sorting on a parallel pointer machine with applications to set expression evaluation, J. ACM, 43 (1996) 331-361.

Digital Library

[16]

D.S. Hirschberg, A.K. Chandra, D.V. Sarwate, Computing connected components on parallel computers, Commun. ACM, 22 (1979) 461-464.

Digital Library

[17]

Y. Han, R.A. Wagner, An efficient and fast parallel connected component algorithm, J. of the ACM, 37 (1990) 626-642.

Digital Library

[18]

S. Halperin, U. Zwick, Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems, 1996.

[19]

S. Halperin, U. Zwick, An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM, J. Comput. Syst. Sci., 53 (1996) 395-416.

Digital Library

[20]

K. Iwama, Y. Kambayashi, A simpler parallel algorithm for graph connectivity, J. Algorithms, 16 (1994) 190-217.

Digital Library

[21]

J. JáJá, Addison¿Wesley, Reading, 1992.

[22]

D.B. Johnson, P. Metaxas, A parallel algorithm for computing minimum spanning trees, J. Algorithms, 19 (1995) 383-401.

Digital Library

[23]

D.B. Johnson, P. Metaxas, Connected components in O(log3/2n) parallel time for CREW PRAM, J. Comput. Syst. Sci., 54 (1997) 227-242.

Digital Library

[24]

D. R. Karger, Random Sampling in Graph Optimization Problems, Ph.D. thesis, Department of Computer Science, Stanford University, 1994.

[25]

D.R. Karger, P.N. Klein, R.E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, J. ACM, 42 (1995) 321-328.

Digital Library

[26]

D.R. Karger, N. Nisan, M. Parnas, Fast connected components algorithms for the EREW PRAM, SIAM J. Comput., 28 (1999) 1021-1034.

Digital Library

[27]

V. King, C.K. Poon, V. Ramachandran, S. Sinha, An optimal EREW PRAM algorithm for minimum spanning tree verification, Inform. Process. Lett., 62 (1997) 153-159.

Digital Library

[28]

C.P. Kruskal, L. Rudolph, M. Snir, Efficient parallel algorithms for graph problems, Algorithmica, 5 (1990) 43-64.

[29]

P.N. Klein, R.E. Tarjan, A randomized linear-time algorithm for finding minimum spanning trees, 1994.

[30]

G. Miller, and, V. Ramachandran, Efficient parallel ear decomposition with applications, unpublished manuscript, MSRI, Berkeley, CA, 1986.

[31]

G.L. Miller, J.H. Reif, Parallel tree contraction, Part 1: Fundamentals, in: Advances in Computing Research, Vol. 5, Randomness and Computation, JAI Press, 1989, pp. 47-72.

[32]

R. Motwani, P. Raghavan, Cambridge Univ. Press, Cambridge, 1995.

[33]

Y. Maon, B. Schieber, U. Vishkin, Parallel ear decomposition search (eds) and st-numbering in graphs, Theoret. Comput. Sci., 47 (1986) 277-298.

Digital Library

[34]

D. Nash, S.N. Maheshwari, Parallel algorithms for the connected components and minimal spanning trees, Inform. Process. Lett., 14 (1982) 7-11.

[35]

N. Nisan, E. Szemerédi, A. Wigderson, Undirected connectivity in O(log1.5n) space, 1992.

[36]

C.A. Phillips, Parallel graph contraction, 1989.

[37]

C.K. Poon, V. Ramachandran, A randomized linear work EREW PRAM algorithm to find a minimum spanning forest, 1997.

[38]

T. Radzik, Computing connected components on EREW PRAM, Technical Report, 94/02, King's College London, 1994.

[39]

V. Ramachandran, Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity, Technical Report, UTEXAS.CS//CS-TR-92-02, University of Texas at Austin, Department of Computer Sciences, 1992.

[40]

V. Ramachandran, Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity, in: Synthesis of Parallel Algorithms, Morgan Kaufmann, 1993, pp. 275-340.

[41]

V. Ramachandran, personal communication, 1996.

[42]

V. Ramachandran, J. Reif, Planarity testing in parallel, J. Comput. Syst. Sci., 49 (1994) 517-561.

Digital Library

[43]

Y. Shiloach, U. Vishkin, An O(logn) parallel connectivity algorithm, J. Algorithms, 3 (1982) 57-67.

[44]

B. Schieber, U. Vishkin, On finding lowest common ancestors: Simplification and parallelization, SIAM J. Comput., 17 (1988) 1253-1262.

Digital Library

[45]

R.E. Tarjan, U. Vishkin, An efficient parallel biconnectivity algorithm, SIAM J. Comput., 14 (1985) 862-874.

Cited By

Farhadi ALiu SShi EAgrawal KPetrank E(2024)Connected Components in Linear Work and Near-Optimal TimeProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659963(395-402)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659963
Götte THinnenthal KScheideler CWerthmann J(2023)Time-optimal construction of overlay networksDistributed Computing10.1007/s00446-023-00442-436:3(313-347)Online publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1007/s00446-023-00442-4
Liu STarjan R(2022)Simple Concurrent Connected Components AlgorithmsACM Transactions on Parallel Computing10.1145/35435469:2(1-26)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1145/3543546
Show More Cited By

Index Terms

Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

Fast Connected Components Algorithms for the EREW PRAM

We present fast and efficient parallel algorithms for finding the connected components of an undirected graph. These algorithms run on the exclusive-read, exclusive-write (EREW) PRAM. On a graph with n vertices and m edges, our randomized algorithm ...
An Optimal Randomised Logarithmic Time Connectivity Algorithm for the EREW PRAM

Improving a long chain of works, we obtain a randomised EREW PRAM algorithm for finding the connected components of a graphG=(V, E) withnvertices andmedges inO(logn) time using an optimal number ofO((m+n)/logn) processors. The result returned by the ...
Work-Time Optimal k-Merge Algorithms on the PRAM

For 2 k n, the k-merge problem is to merge a collection of k sorted sequences of total length n into a new sorted sequence. The k-merge problem is fundamental as it provides a common generalization of both merging and sorting. The main contribution of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Algorithms

Journal of Algorithms Volume 39, Issue 1

April 2001

135 pages

ISSN:0196-6774

Editors:
ZVI Galil
Columbia Univ., New York
,
David S. Johnson
AT&T Lab—Research, Fordham Park, New Jersey
,
Donald E. Knuth
Stanford Univ., Stanford, California

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 April 2001

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Farhadi ALiu SShi EAgrawal KPetrank E(2024)Connected Components in Linear Work and Near-Optimal TimeProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659963(395-402)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659963
Götte THinnenthal KScheideler CWerthmann J(2023)Time-optimal construction of overlay networksDistributed Computing10.1007/s00446-023-00442-436:3(313-347)Online publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1007/s00446-023-00442-4
Liu STarjan R(2022)Simple Concurrent Connected Components AlgorithmsACM Transactions on Parallel Computing10.1145/35435469:2(1-26)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1145/3543546
Götte THinnenthal KScheideler CWerthmann JMiller ACensor-Hillel K(2021)Time-Optimal Construction of Overlay NetworksProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467932(457-468)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467932
López-Martínez AMukhopadhyay SNanongkai DAgrawal KAzar Y(2021)Work-Optimal Parallel Minimum Cuts for Non-Sparse GraphsProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461806(351-361)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461806
Jayanti STarjan R(2021)Concurrent disjoint set unionDistributed Computing10.1007/s00446-020-00388-x34:6(413-436)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s00446-020-00388-x
Liu STarjan RZhong PScheideler CSpear M(2020)Connected Components on a PRAM in Log Diameter TimeProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400249(359-369)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400249
Wang YGu YShun JMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Theoretically-Efficient and Practical Parallel DBSCANProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3380582(2555-2571)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3380582
Acar UAnderson DBlelloch GDhulipala LScheideler CBerenbrink P(2019)Parallel Batch-Dynamic Graph ConnectivityThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323196(381-392)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323196
Stergiou SRughwani DTsioutsiouliklis KChang YZhai CLiu YMaarek Y(2018)Shortcutting Label Propagation for Distributed Connected ComponentsProceedings of the Eleventh ACM International Conference on Web Search and Data Mining10.1145/3159652.3159696(540-546)Online publication date: 2-Feb-2018
https://dl.acm.org/doi/10.1145/3159652.3159696
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents