Graph Connectivity References

1

Ajit Agrawal, Lena Nekludova, and Willie Lim. A parallel O(log N) algorithm for finding connected components in planar images. In Proceedings International Conference on Parallel Processing, pages 783-786, August 1987.

2

B. Awerbuch, A. Baratz, and D. Peleg. Cost-sensitive analysis of communication protocols. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, pages 177-187, August 1990.

3

Baruch Awerbuch and Yossi Shiloach. New connectivity and MSF algorithms for Ultracomputer and PRAM. In Proceedings International Conference on Parallel Processing, pages 175-179, 1983.

4

S. Bhawmik, C.J. Lin, K.-T. Cheng, and V.D. Agrawal. Pascant: a partial scan and test generation system. In Proceedings of the IEEE 1991 Custom Integrated Circuits, May 1991.

5

Guy E. Blelloch. NESL: A nested data-parallel language (version 2.6). Technical Report CMU-CS-93-129, School of Computer Science, Carnegie Mellon University, April 1993.

6

R. C. Brower, Pablo Tamayo, and Bryant York. A parallel multigrid algorithm for percolation clusters. Journal of Statistical Physics, 63(1/2):73-88, 1991.

7

P.D. Coddington and C.F. Baillie. Parallel cluster algorithms. In LATTICE 90. International Conference on Lattice Field Theory, pages 17-79, October 1990.

8

S. K. Das, N. Deo, and S. Prasad. Parallel graph algorithms for hypercube computers. Parallel Computing, 13(2):143-158, February 1990.

9

H.G. Evertz. Vectorized cluster search. In LATTICE 91. International Symposium on Lattice Field Theory. Nuclear Physics B, Proceedings Supplements; vol.26B, pages 620-622, May 1992.

10

Hillel Gazit. An optimal randomized parallel algorithm for finding connected components in a graph. SIAM Journal of Computing, 20(6), December 1991.

11

P. S. Gopalakrishnan, I. V. Ramakrishnan, and Laveen N. Kanal. An efficient connected components algorithm on a mesh-connected computer. Technical Report TR-1467, University of Maryland, 1987.

12

John Greiner. A comparison of data-parallel algorithms for connected components. Technical Report CMU-CS-93-191, School of Computer Science, Carnegie Mellon University, August 1993.

13

H.D. Groger. A new partition lemma for planar graphs and its application to circuit complexity. In Fundamentals of Computation Theory. 8th International Conference, FCT '91 Proceedings, pages 220-229, September 1991.

14

T. Hagerup. Optimal parallel algorithms on planar graphs. Information and Computation, 84(1):71-96, January 1990.

15

S. Hambrusch and L. TeWinkel. A study of connected component labeling algorithms on the MPP. In Proceedings of the Third International Conference on Supercomputing, pages 477-483, May 1988.

16

Y. Han and R. A. Wagner. An efficient and fast parallel-connected component algorithm. Journal of the Association for Computing Machinery, 37(3):626-642, July 1990.

17

D. S. Hirschberg, A. K. Chandra, and D. V. Sarwate. Computing connected components on parallel computers. Communications of the ACM, 22(8):461-464, 1979.

18

M. Houtman and E. Sterken. The structure of macroeconomic models. In Dynamic Modelling and Control of National Economies 1989: Selected Papers from the 6th IFAC Symposium, pages 281-286, June 1989.

19

Z. Jovanovic. Software pipelining of loops by pipelining strongly connected components. In Proceedings of the International Conference on System Sciences, pages 351-365, January 1991.

20

Ming-Ying Kao and Gregory E. Shannon. Linear-processor NC algorithms for planar directed graphs. Technical Report 306, Indiana University, Bloomington, Computer Science Dept, 1990.

21

William Lim, Ajit Agrawal, and Lena Nekludova. A fast parallel algorithm for labeling connected components in image arrays. Technical Report NA86-2, Thinking Machines Corporation, December 1986.

22

T.J. Marlowe and B.G. Ryder. An efficient hybrid algorithm for incremental data flow analysis. In Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, pages 184-196, January 1990.

23

Hidetoshi Mino. A vectorized algorithm for cluster formation in the Swendsen-Wang dynamics. Computer Physics Communications, 66:25-30, 1991.

24

Panos M. Paradlos and Chandra S. Rentala. Computational aspects of a parallel algorithm to find the connected components of a graph. Technical Report CS-89-01, Pennsylvania State University Department of Computer Science, 1989.

25

Cynthia A. Phillips. Parallel graph contraction. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, pages 148-157, June 1989.

26

John H. Reif. Optimal parallel algorithms for integer sorting and graph connectivity. Technical Report TR-08-85, Harvard University, March 1985.

27

J. T. Schwartz, R. B. K. Dewar, E. Dubinsky, and E. Schonberg. Programming with Sets: An Introduction to SETL. Springer-Verlag, New York, 1986.

28

H.-C. Shih, P.G. Kovijanic, and R. Razdan. A global feedback detection algorithm for VLSI circuits. In Proceedings. 1990 IEEE International Conference on Computer Design: VLSI in Computers and Processors, pages 37-40, September 1990.

29

Yossi Shiloach and Uzi Vishkin. An O(log N) parallel connectivity algorithm. Journal of Algorithms, 3:57-67, 1982.

30

R. H. Swendsen and J.-S. Wang. Physical Review Letters, 58(86), 1987.

31

Uzi Vishkin. An optimal parallel connectivity algorithm. Discrete Applied Mathematics, 9(2):235-240, 1985.

32

Jinwoon Woo and Sartaj Sahni. Hypercube computing: Connected components. Technical Report TR-88-50, University of Minnesota Computer Science Department, July 1988.

33

P.J. Wright and R.J. Offen. Optimized redundant cell collection in a parallel graph reduction machine using reference counts. Algorithms and Parallel VLSI Architectures, pages 373-382, June 1990.

34

Xue Dong Yang. An improved algorithm for labeling connected components in a binary image. Technical Report 89-981, Cornell University Department of Computer Science, March 1989.

Back to the Graph Connectivity page.