A new graph triconnectivity algorithm and its parallelization

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

   Google Scholar 

2. R. Cole, U. Vishkin: Approximate and exact parallel scheduling with applications to list, tree and graph problems,Proc. 27th Ann. IEEE Symp. on Foundations of Comp. Sci. 1986, 478–491.

3. S. Even:Graph Algorithms, Computer Science Press, Rockville, MD, 1979.

   Google Scholar 

4. J. E. Hopcroft, R. E. Tarjan: Dividing a graph into triconnected components,SIAM J. Comput. 2 (1973), 135–158.

   Google Scholar 

5. J. E. Hopcroft, R. E. Tarjan: Finding the triconnected components of a graph, TR 72-140, Computer Science Department, Cornell University, Ithaca, NY, 1972.

   Google Scholar 

6. J. Ja'Ja, J. Simon: Parallel algorithms in graph theory: planarity testing,SIAM J. Comput. 11 (1982), 314–328.

   Google Scholar 

7. A. Kanevsky, V. Ramachandran: Improved algorithms for graph four-connectivity,Jour. Comput. Syst. Sci. 42 (1991), 288–306.

   Google Scholar 

8. R. M. Karp, V. Ramachandran: Parallel algorithms for shared memory machines,Handbook of Theoretical Computer Science, J. Van Leeuwen, ed., North Holland, 1990, 869–941.

9. L. Lovász: Computing ears and branchings in parallel,Proc. 26th IEEE Ann. Symp. on Foundations of Comp. Sci. 1985, 464–467.

10. Y. Maon, B. Schieber, U. Vishkin: Parallel ear decomposition search (EDS) and st-numbering in graphs,Theoretical Comput. Sci. 47 (1986), 277–298.

    Google Scholar 

11. G. L. Miller, V. Ramachandran: Efficient parallel ear decomposition with applications, unpublished manuscript, MSRI, Berkeley, CA, January 1986.

    Google Scholar 

12. G. L. Miller, V. Ramachandran: A new graph triconnectivity algorithm and its parallelization,Proc. 19th Annual ACM Symp. on Theory of Computing, 1987, 254–263.

13. G. L. Miller, J. H. Reif: Parallel tree contraction and its applications,Proc. 26th IEEE Symp. on Foundations of Comp. Sci., 1985, 478–489.

14. V. Ramachandran, U. Vishkin: Efficient parallel triconnectivity in logarithmic time,VLSI Algorithms and Architectures, Springer Verlag LNCS319 (1988), 33–42.

    Google Scholar 

15. R. E. Tarjan, U. Vishkin: Finding biconnected components and computing tree functions in logarithmic parallel time,SIAM J. Comput. 14 (1985), 862–874.

    Google Scholar 

16. W. T. Tutte:Connectivity in Graphs, University of Toronto Press, 1966.

17. H. Whitney: Non-separable and planar graphs,Trans. Amer. Math. Soc. 34 (1932), 339–362.

    Google Scholar 

Download references