Skip to main content
SpringerLink
Log in

Computing biconnected components on a hypercube

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

We describe two hypercube algorithms to find the biconnected components of a dense connected undirected graph. One is a modified version of the Tarjan-Vishkin algorithm and the other is an adaptation of Read's sequential algorithm. The two hypercube algorithms were experimentally evaluated on an NCUBE/7 MIMD hypercube computer. The two algorithms have comparable performance, and efficiencies as high as 0.7 were observed on dense graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

We’re sorry, something doesn't seem to be working properly.

Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

References

  • Aho, A., Hopcroft, J., and Ullman, J. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass.

    Google Scholar 

  • Aho, A., Hopcroft, J., and Ullman, J. 1983. Data Structures and Algorithms. Addison-Wesley, Reading, Mass.

    Google Scholar 

  • Dekel, E., Nassimi, D., and Sahni, S. 1981. Parallel matrix and graph algorithms. SIAM J. Computing, 10, 4 (Nov.), 657–675.

    Google Scholar 

  • Gopalakrishnan, P.S., Ramakrishnan, I.V., and Kanal, L.N. 1985. Computing tree functions on mesh-connected computers. In Proc., 1985 Internat. Conf. on Parallel Processing, pp. 703–710.

  • Gustafson, J. 1988. Reevaluating Amdahl's Law. CACM, 31, 5 (May), 532–533.

    Google Scholar 

  • Horowitz, E., and Sahni, S. 1978. Fundamentals of Computer Algorithms. Comp. Sci. Press, Potomac, Md.

    Google Scholar 

  • Horowitz, E., and Sahni, S. 1986. Fundamentals of Data Structures in Pascal, 2nd ed. Comp. Sci. Press, Potomac, Md.

    Google Scholar 

  • Kumar, V., Nageshwara, V., and Ramesh, K. 1988. Parallel depth first search on the ring architecture. In Proc., 1988 Internat. Conf. on Parallel Processing, The Penn. Univ. Press, pp. 128–132.

  • Lai, T., and Sahni, S. 1984. Anomalies in parallel branch and bound algorithms. CACM, 27, 6 (June), 594–602.

    Google Scholar 

  • Li, G., and Wan, B. 1986. Coping with anomalies in parallel branch-and-bound algorithms. IEEE Trans. Comps., C-35, 6 (June), 568–572.

    Google Scholar 

  • Nassimi, D., and Sahni, S. 1980. Finding connected components and connected ones on a mesh-connected computer. SIAM J. Computing, 9, 4 (Nov.), 744–757.

    Google Scholar 

  • Nassimi, D., and Sahni, S. 1981. Data broadcasting in SIMD computers. IEEE Trans. Comps., C-30, 2 (Feb.), 101–107.

    Google Scholar 

  • Quin, M., and Deo, N. 1986. An upper bound for the speedup of parallel branch-and-bound algorithms. BIT, 26, 1 (Mar.), 35–43.

    Google Scholar 

  • Ranka, S., and Sahni, S. 1988. Image template matching on MIMD hypercube multicomputers. In Proc., 1988 Internat. Conf. on Parallel Processing, vol. 3, Algorithms and Applications, The Penn. Univ. Press, pp. 92–99.

  • Ranka, S., and Sahni, S. 1989. Computing Hough transforms on hypercube multicomputers. Tech. rept. 89–1, Dept. of Comp. Sci., Univ. of Minn., Minneapolis, Minn.

    Google Scholar 

  • Rao, V.N., and Kumar, V. 1987. Parallel depth-first search. Part 1, Implementation. Internat. J. Parallel Programming, 16: 479–499.

    Google Scholar 

  • Read, R. 1969. Teaching graph theory to a computer. In Recent Progress in Combinatorics (W. Tutte, ed.), Academic Press, pp. 161–173.

  • Sheu, J.P., Kuo, N.L., and Chen, G.H. 1990. Graph search algorithms and maximum bipartite matching algorithm on the hypercube network model. Parallel Computing, 13: 245–251.

    Google Scholar 

  • Shiloach, Y., and Vishkin, U. 1982. An O(log n) parallel connectivity algorithm. J. Algorithms, 3, 1: 57–67.

    Google Scholar 

  • Tarjan, R. 1972. Depth first search and linear graph algorithms. SIAM J. Computing, 1: 146–160.

    Google Scholar 

  • Tarjan, R., and Vishkin, U. 1985. An efficient parallel biconnectivity algorithm. SIAM J. Computing, 14, 4 (Nov.), 862–874.

    Google Scholar 

  • Woo, J., and Sahni, S. 1988. Hypercube computing: Connected components. In IEEE Proc., Workshop on the Future Trends of Distributed Computing Systems in the 1990s, IEEE Comp. Soc. Press, pp. 408–417.

  • Wyllie, J. 1979. The compexity of parallel computation. Tech. rept. TR79–387, Dept. of Comp. Sci., Cornell Univ., Ithaca, N.Y.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dankook University, Seoul, Korea

    Jinwoon Woo

  2. Computer and Information Sciences and Engineering, University of Florida, 32611-2024, Gainesville, Florida, USA

    Sartaj Sahni

Authors
  1. Jinwoon Woo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sartaj Sahni
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported in part by the National Science Foundation under grants DCR84-20935 and MIP 86-17374.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Woo, J., Sahni, S. Computing biconnected components on a hypercube. J Supercomput 5, 73–87 (1991). https://doi.org/10.1007/BF00155859

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00155859

Keywords

Search

Navigation