Résumé: Cette thèse est principalement dédiée a l'étude des propriétés algorithmiques et combinatoires des ensembles ordonnes. Les travaux qui y sont exposes peuvent être regrouper suivant quatre principaux thèmes: -les exécutions reparties: nous définissons un cadre adapte au calcul de mesures attachées a une exécution repartie. Puis nous proposons une mesure deconcurrence et nous étudions ses propriétés combinatoires; -les extensions d'intervalles d'un ensemble ordonne: nous caractérisons les extensions d'intervalles minimales d'un ordre, nous etudions leurs propriétés et nous proposons des algorithmes permettant d'en calculer le nombre; -le nombre chromatique du diagramme d'un ensemble ordonne: nous exhibons des classes d'ordres pour lesquelles le nombre chromatique cherche est borne et d'autres pour lesquelles ce nombre est arbitrairement grand; -la réduction et la fermeture transitive d'un graphe oriente sans circuit: nous proposons des algorithmes permettant de calculer la réduction ou la fermeture transitive en temps linéaire sur certaines classes de graphes.

Edition: Montpellier: Université des Sciences et Techniques de Montpellier 2
Langue: Français
Collation: 254 p. ill. ;30 cm
Diplôme: Doctorat
Etablissement de soutenance: Université des Sciences et Techniques de Montpellier 2

Note: Bibliogr.pp.195-200; Annexe pp.201-254