. Adler, Parallel sorting with limited bandwith, 7th ACM Symposium on Parallel Algorithms and Architectures (SPAA'95), pp.129-136, 1995.
DOI : 10.1145/215399.215431
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.869

M. Anderson, R. Anderson, and G. Miller, Deterministic parallel list ranking, Proceedings Third Aegean Workshop on Computing, pp.81-90, 1988.

M. Anderson, R. Anderson, and G. Miller, A simple randomized parallel algorithm for list-ranking, Information Processing Letters, vol.33, issue.5, pp.269-279, 1990.
DOI : 10.1016/0020-0190(90)90196-5

. Bäumer, . Dittrich, A. Bäumer, and W. Dittrich, Parallel Algorithms for Image Processing: Practical Algorithms with Experiments, Proc. of the 10th International Parallel Processing Symposium (IPPS'96), pp.429-433, 1996.

. Blelloch, A Comparison of Sorting Algorithms for the Connection Machine CM2, Symposium on Parallel Algorithms and Architectures (SPAA'91), pp.3-16, 1991.

. Caceres, Efficient parallel graph algorithms for coarse grained multicomputers and BSP, Proceedings of the 24th International Colloquium ICALP'97, pp.390-400, 1997.
DOI : 10.1007/3-540-63165-8_195

C. Colbourn, On testing isomorphism of permutation graphs, Networks, vol.1, issue.1, pp.13-21, 1981.
DOI : 10.1002/net.3230110103

C. , V. Cole, R. Vishkin, and U. , Approximate parallel scheduling, part I: The basic technique with applications t optimal INRIA and parallel algorithms for permutation graphs, 1988.

. Hsu, Implementation of parallel graph algorithms on a massively parallel SIMD computer with virtual processing, Proc. 9th International Parallel Processing Symposium, pp.106-112, 1995.

. Hsu, Parallel Implementation of Algorithms for Finding Connected Components in Graphs, Parallel Algorithms : Third DIMACS Implementation Challenge, pp.395-416, 1997.

J. Jájá, An Introduction to Parallel Algorithm, 1992.

. Karp, . Ramachandran, R. Karp, and V. Ramachandran, Parallel Algorithms for Shared-Memory Machines, Handbook of Theoretical Computer Science Volume A: Algorithms and Complexity, pp.869-942, 1990.
DOI : 10.1016/B978-0-444-88071-0.50022-9

. Krishnamurthy, Connected Components on Distributed Memory Machines, Third DIMACS Implementation Challenge, pp.1-21, 1997.

. Krizanc, . Saarimaki, D. Krizanc, and A. Saarimaki, Bulk synchronous parallel: practical experience with a model for parallel computing, Parallel Computing, vol.25, issue.2, pp.159-181, 1999.
DOI : 10.1016/S0167-8191(98)00106-9

. Kumar, Connected-Components Algorithms for Mesh-Connected Parallel Computers, Third DIMACS Parallel Challenge, 1997.

F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays . Trees . Hypercubes, 1992.

. Lumetta, Towards modeling the performance of a fast connected components algorithm on parallel machines, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM) , Supercomputing '95, 1995.
DOI : 10.1145/224170.224275

. Pneuili, Transitive orientation of graphs and identification of permutation graphs, Journal canadien de math??matiques, vol.23, issue.0, 1971.
DOI : 10.4153/CJM-1971-016-5

S. Preparata, F. Preparata, and M. Shamos, Computational Geometry: an Introduction, 1985.
DOI : 10.1007/978-1-4612-1098-6

M. Reid-miller, List ranking and list scan on the Cray C-90, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures , SPAA '94, 1994.
DOI : 10.1145/181014.181049

J. F. Sibeyn, Better Tradeoffs for Parallel List Ranking, Proceedings of the 9th ACM Symposium on Parallel Algorithms and Architectures (SPAA'97), pp.221-230, 1997.

. Sibeyn, Practical Parallel List Ranking, Journal of Parallel and Distributed Computing, vol.56, issue.2, pp.156-180, 1999.
DOI : 10.1006/jpdc.1998.1508

V. Spinrad, J. Spinrad, and J. Valdes, Recognition and isomorphism of two dimensional partial orders, 10th Coll. on Automata, Language and Programming., number 154 in Lecture Notes in Computer Science, pp.676-686, 1983.
DOI : 10.1007/BFb0036947

A. Tanenbaum, RE- SEAUX, 1997.

L. Valiant, A bridging model for parallel computation, Communications of the ACM, vol.33, issue.8, pp.103-111, 1990.
DOI : 10.1145/79173.79181

J. Wyllie, The Complexity of Parallel Computations, 1979.

I. Unité-de-recherche-inria-rocquencourt-domaine-de-voluceau-rocquencourt-bp, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Rennes : IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe -38330 Montbonnot-St, pp.105-78153, 2004.

I. De-voluceau-rocquencourt, BP 105 -78153 Le Chesnay Cedex (France) http://www.inria.fr ISSN, pp.249-6399