Quelques algorithmes parallèles et séquentiels de traitement de graphes
et applications

L. Viennot

IBP-Litp 1996/Th/06: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 Litp / Litp research reports
167 pages - Janvier/January 1997 - French document.

PostScript : Ko /Kb

Titre / Title: Quelques algorithmes parallèles et séquentiels de traitement de graphes
et applications


Résumé : Quelques algorithmes parallèles et séquentiels de traitement de graphes et applications
Cette thèse présente un point de vue algorithmique parllèle et séquentiel sur le traitement des graphes.
Le chapitre 1 est consacré au modèle PRAM qui est le modèlede parallélisme le plus simple qui soit : plusieurs processeurs ont accès à une mémoire partagée. Même avec la simplification apportée par le modèle, certains problèmes restent difficiles à résoudre. La section 1.1 introduit une repr ésentation adaptée auxtraitement algorithmique des ordres de dimension fixée d et permet de calculer une représentation classique de l'ordre, ce calcul est lié aux traitement de requêtes géométriques dans un espace de dimension d . La section 1.2 est consacrée à la reconnaissance en parallèledes ordres N-free et la section 1.3 traite de la reconnaissance des graphes de comparabilité. D'une manière générale, l'étude de classes particulières de graphes permet de résoudre des problèmes qui sont difficilesdans le cas général en utilisant une structure algorithmique sous-jacenteà la classe considérée. Le problème de la reconnaissance consiste souvent à trouvercette structure.
Le chapitre 2 est consacré au modèle CGM qui est un modèle de machine parallèle dite << à gros grain >> qui priviligie l'étude du placement distribué des données d'un problème, c'est-à-dire sur les différentes mémoires des ordinateurs qui vont travailler ensemble sur le problème. Ce chapitre reprend les problèmes abordés dans le modèle PRAM et en fournit des solutions dans le modèle CGM. Un algorithme de list-ranking est de plus présenté dans la section 2.2, cet outil intervenant dans le calcul des composantes connexes d'un graphe dans ce modèle.
Le chapitre 3 est consacré à un << modèle de calcul >> très particulier issu d'un problème de téléphonie GSM qui nous a été posé par Nortel Matra Cellular. Ce chapitre regroupe d'une part les différentes idées algorithmiques qui s'appliquent à un telproblème soumis à de multiples contraintes et d'autre part des simulations permettant d'évaluer la pertinence des différentes idées. Ce problème est de nature continue mais on peut néanmoins y apporter des solutions issues de l'algorithmique discrète telles que les techniques liées aux composantes connexes d'un graphe. Par souci de continuité, un algorithme de composante connexes est donné dans chacun des trois modèles abordés.
Enfin, le chapitre 4 est consacré à une nouvelle technique algorithmique : l'affinage de partition. La section 4.1 tente de cerner cette technique et montre les ressemblances entre différents algorithmes existants. Cette technique nous permet de généraliser certains de ces algorithmes à la résolution d'autres problèmes proches, comme le calcul des jumaux. L'affinage de partition nous permet ensuite dans la section 4.2 de donner des algorithmes simples pour les problèmes de la reconnaissance des graphes d'intervalles et de l'orientation transitive, deux problèmes dont les solution algorithmiques efficaces étaient jusque là très difficiles à implanter et reposaient sur des structures de données complexes.

Abstract : Parallel and Sequential Graph Algorithms and Applications

This thesis introcduces graph algorithms from the point of view of parallel and sequential models.

Chapter 1 deals with the PRAM model which is the simplest existing parallel model: several processors work together on a shared memory. Even with this simplification, some problems remain very difficult. Section 1.1 introduces a representation of orders of dimension d that eanables efficient computations and also eanables to compute a classical representation of the order, this computation is linked to range queries in a d dimensionnal space. Section 1.2 deals with N-free order recognition and Section 1.3 deals with comparability graph recognition. In general, the study of special classes of graphs allows to solve problems that are difficult in the general case thanks to underlying structures of the class considered. The recognition problem consists in finding this structure.

Chapter 2 deals with the CGM model which is a "coarse grain" model. This model is well suited for the study of data distribution among the memories of the processors that are going to work together on the problem. This chapter gives CGM solutions to the problems introduced in Chapter 1. In addition, Section 2.2 introduces a "list-ranking" algorithm, this tool is used in the connected components computations.

Chapter 3 deals with a very special "computation model" coming from a problem of the cellular phones GSM system. This chapter introduces different algorithmic ideas which may solve this problem with multiple constraints, and simulation results to compare these ideas. The nature of this problem is continuous but discrete algorithmic ideas also apply (ideas linked to connected components). For the sake of continuity, a connected component algorithm is proposed in each of the three models considered.

Chapter 4 deals with a new algorithmic technique: partition refining. Section 4.1 tries to give a general framework for this idea and shows the similarity between different existing algorithms. This technique allows to generalize some of these algorithms to the resolution of other similar problems. Partition refining is also used to give simple interval graph recognition and transitive orientation algorithms. Up to now, the efficient solutions to these problems were difficult to implement and used complex data structures.


Publications internes Litp 1996 / Litp research reports 1996