. 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.
DOI : 10.1007/bfb0040376

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.

. Bilardi, BSP vs LogP, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures , SPAA '96, pp.25-31, 1996.
DOI : 10.1145/237502.237504

. 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 parallel list ranking in logarithmic time, SIAM J. Computing, vol.17, issue.1, pp.128-142, 1988.

C. , V. Cole, R. Vishkin, and U. , Faster optimal prefix sums and list ranking, Information and Computation, vol.81, issue.3, pp.344-352, 1989.
DOI : 10.1016/0890-5401(89)90036-9
URL : http://doi.org/10.1016/0890-5401(89)90036-9

. Cormen, Introduction to Algorithms, 1990.

. Culler, LogP: Towards a Realistic Model of Parallel Computation, Proceeding of 4-th ACM SIGPLAN Symp. on Principles and Practises of Parallel Programming, pp.1-12, 1993.

. Dehne, Scalable parallel geometric algorithms for coarse grained multicomputers, Proceedings of the ninth annual symposium on Computational geometry , SCG '93, pp.298-307, 1993.
DOI : 10.1145/160985.161154
URL : https://hal.archives-ouvertes.fr/inria-00074853

G. Dehne, F. Dehne, and S. Götz, Practical parallel algorithms for minimum spanning trees, Proceedings Seventeenth IEEE Symposium on Reliable Distributed Systems (Cat. No.98CB36281), pp.366-371, 1998.
DOI : 10.1109/RELDIS.1998.740525
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.1936

S. Dehne, F. Dehne, and S. W. Song, Randomized parallel list ranking for distributed memory multiprocessors, Proc. 2nd Asian Computing Science Conference ASIAN'96, pp.1-10, 1996.
DOI : 10.1007/BF02700044
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.6004

A. C. Dusseau, Fast parallel sorting under LogP: experience with the CM-5, IEEE Transactions on Parallel and Distributed Systems, vol.7, issue.8, pp.791-805, 1996.
DOI : 10.1109/71.532111

A. Ferreira, Parallel and communication algorithms for hypercube multiprocessors, Handbook of Parallel and Distributed Computing, 1996.

. Ferreira, Parallel computation on interval graphs using PC clusters: Algorithms and experiments, Proc. of International EuroPar Conference, pp.875-886, 1998.
DOI : 10.1007/BFb0057943
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.6223

W. Fortune, S. Fortune, and J. Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, pp.114-118, 1978.
DOI : 10.1145/800133.804339

I. Forum and M. P. Forum, Document for a standard message-passing interface, 1993.

I. Foster, Designing and building parallel programs, 1995.

. Geist, PVM-Parallel Virtual Machine: AUsers' Guide and Tutorial for Networked Parallel Computing, Computers in Physics, vol.9, issue.6, 1994.
DOI : 10.1063/1.4823450

S. Gerbessiotis, A. V. Gerbessiotis, and C. J. Siniolakis, Deterministic sorting and randomized median finding on the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures , SPAA '96, pp.223-232, 1996.
DOI : 10.1145/237502.237561

A. V. Gerbessiotis and L. G. Valiant, Direct Bulk-Synchronous Parallel Algorithms, Journal of Parallel and Distributed Computing, vol.22, issue.2, pp.251-267, 1994.
DOI : 10.1006/jpdc.1994.1085
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.9332

M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, 1980.

M. Goodrich, Communication-Efficient Parallel Sorting, Proc. of 28th Symp. on Theory of Computing, 1996.
DOI : 10.1137/S0097539795294141

. Goudreau, Towards efficiency and portability, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures , SPAA '96, pp.1-12, 1996.
DOI : 10.1145/237502.237503

J. Greiner, A comparison of parallel algorithms for connected components, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures , SPAA '94, pp.16-25, 1994.
DOI : 10.1145/181014.181021

I. Guérin-lassous-]-guérin-lassous, Algorithmes parallèles de traitement de graphes : une approche basée sur l'analyse expérimentale, 1999.

L. Guérin, G. Lassous, I. Gustedt, and J. , List ranking on a coarse grained multiprocessor, 1999.

L. Guérin, G. Lassous, I. Gustedt, and J. , List ranking on PC clusters, 2000.

L. Guérin, M. Lassous, I. Morvan, and M. , Some results on ongoing research on parallel implementation of graph algorithms: the case of permutation graphs, Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications, pp.325-330, 1998.

L. Guérin, I. Thierry-]-guérin-lassous, and É. Thierry, Generating random permutations in the parallel coarse grained models framework, 2000.

. Gustedt, A compact data structure and parallel algorithms for permutation graphs, WG '95 21st Workshop on Graph-Theoretic Concepts in computer Science. Lecture Notes in Computer Science 1017, 1995.
DOI : 10.1007/3-540-60618-1_89
URL : https://hal.archives-ouvertes.fr/inria-00471607

. 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

. Keeton, Logp Quantified: The Case for Lowoverhead Local Area Networks, Hot Interconnects III: A Symposium on High Performance Interconnects, 1995.

. 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.

. Löwe, On Linear Schedules of Tasks Graphs on Generalized LogP-Machines, LNCS, editor, Europar'97, pp.895-904, 1997.

. 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, pp.160-175, 1971.
DOI : 10.4153/CJM-1971-016-5

. Shiloach, . Vishkin, Y. Shiloach, and U. Vishkin, An O log n¡ parallel connectivity algorithm, Journal of Algorithms, issue.1, pp.57-67, 1983.
DOI : 10.1016/0196-6774(82)90008-6

J. F. Sibeyn, Better trade-offs for parallel list ranking, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures , SPAA '97, pp.221-230, 1997.
DOI : 10.1145/258492.258514

. 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
URL : http://hdl.handle.net/11858/00-001M-0000-000F-3604-B

J. Spinrad, Dimension and algorithms, Orders, Algorithms and Applications, pp.33-52, 1994.
DOI : 10.1007/BFb0019425

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

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

L. Viennot, Quelques algorithmes parallèles et séquentiels de traitement des graphes et applications, 1996.

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

I. Unité-de-recherche, . Lorraine, V. Technopôle-de-nancy-brabois, I. Lès-nancy-unité-de-recherche, and . Rennes, Campus scientifique, 615 rue du Jardin Botanique Irisa, Campus universitaire de Beaulieu, 35042 RENNES Cedex Unité de recherche INRIA Rhône-Alpes, p.78153, 2004.