Résumé: Cette thèse consacre des trvaux de recherche sur des problèmes de complexité dans les graphes. Les résultats qui y sont présentés peuvent être classés en trois rubrique: prpblèmes d'éxistence de longs cycles alternés dans des graphes complets arête-colorés, problèmes de construction de routages dans les réseaux d'interconnexion, problèmes du transversal d'hypergraphes minimum.Un accent particulier est mis sur la complexité des problèmes étudiés. Différentes approches sont proposées: recherche d'algorithmes efficaces, preuves de NP-complétude, approche probabiliste et recherche

:
Langue: Français
Collation: 131 p. ill. ;30 cm
Diplôme: Doctorat
Etablissement de soutenance: Paris, Université Paris Sud centre d'Orsay
Spécialité: Science
Index décimal 510 .Mathématiques
Thème Mathématiques

Mots clés:
Graphes
Complexité
Tournois bipartis
Indices de transmission

Note: Bibliogr.pp.131-140