| Titre : | Problèmes Algorithmiques dans les Réseaux Tout-Optique | | Type de document : | texte imprimé | | Auteurs : | J. PALAYSI, Auteur | | Année de publication : | 2002 | | Langues : | Français (fre) | | Tags : | RESEAUX WDM MINIMISATION DE CHARGE RESEAUX WDM MINIMISATION DE CHARGE COLORATION DE CHAINES ROUTAGE TOUT-OPTIQUE COLORATION SUR LISTES GRAPHES ALGORITHMES COMPLEXITE NETWORKS WDM LOAD MINIMIZATION PATH COLORING ALL-OPTICAL ROUTING LIST COLORING GRAPHS AGORITHMS COMPLEXITY | | Index. décimale : | THE Thèses de doctorat | | Résumé : | L'avènement des réseaux tout-optique fait apparaître ou reapparaîre des problèmes algorithmiques théoriques parmi lesquels : la Minimisation de Charge, la Coloration de Chaînes, le Routage Tout-Optique et la Coloration sur Listes. Les trois premiers problèmes sont NP difficiles en général. Nous montrons plus precisément que la Coloration de Chaînes dans les grilles et les tores est No-APX. Nous montrons également qu'il existe des algorithmes approchants pour ces trois problèmes lorsque les instances sont réduites à des réseaux en forme de grille ou de tore et que les routes recherchées doivent être de type ligne-colonne. La Coloration sur Listes est un problème NP-complet en général. Il s'agit d'une généralisation du problème bien connu de coloration des sommets d'un graphe. Nous étudions d'abord l'intérêt de connaître une coloration classique d'un graphe dans la résolution d'une instance de Coloration sur Listes. Nous nous intéressons ensuite à la liste-colorabilité des graphes bipartis.
The raising of all-optical networks makes several theoretical algorithmic problems appear or reappear among which we can find : Load Minimization, Path Coloring, All-Optical Routing and List Coloring. The first three problems are NP-hard in general. We show more precisely that Path Coloring in meshes and toroidal meshes is No-APX. We also show that these problems can be solved by approximation algorithms if instances are reduced to mesh networks or toroidal mesh networks and if the paths we are looking for have row-column type. The List Coloring is a NP-complete problem in general. This is a variation and a generalization of the well-known vertex coloring problem. First, we study if knowing a classic coloring of a graph helps to solve an instance of List Coloring. Then we focus on bipartite graph choosability. | | Directeur(s) de thèse : | KONIG J.C. | | Co-directeur(s) de thèse : | COGIS O. | | Président du jury : | CHEIN M. | | Rapporteur(s) : | GERMA A.;BARTH D. | | Date de soutenance : | 19/12/2002 |
Problèmes Algorithmiques dans les Réseaux Tout-Optique [texte imprimé] / J. PALAYSI, Auteur . - 2002. Langues : Français ( fre) | Tags : | RESEAUX WDM MINIMISATION DE CHARGE RESEAUX WDM MINIMISATION DE CHARGE COLORATION DE CHAINES ROUTAGE TOUT-OPTIQUE COLORATION SUR LISTES GRAPHES ALGORITHMES COMPLEXITE NETWORKS WDM LOAD MINIMIZATION PATH COLORING ALL-OPTICAL ROUTING LIST COLORING GRAPHS AGORITHMS COMPLEXITY | | Index. décimale : | THE Thèses de doctorat | | Résumé : | L'avènement des réseaux tout-optique fait apparaître ou reapparaîre des problèmes algorithmiques théoriques parmi lesquels : la Minimisation de Charge, la Coloration de Chaînes, le Routage Tout-Optique et la Coloration sur Listes. Les trois premiers problèmes sont NP difficiles en général. Nous montrons plus precisément que la Coloration de Chaînes dans les grilles et les tores est No-APX. Nous montrons également qu'il existe des algorithmes approchants pour ces trois problèmes lorsque les instances sont réduites à des réseaux en forme de grille ou de tore et que les routes recherchées doivent être de type ligne-colonne. La Coloration sur Listes est un problème NP-complet en général. Il s'agit d'une généralisation du problème bien connu de coloration des sommets d'un graphe. Nous étudions d'abord l'intérêt de connaître une coloration classique d'un graphe dans la résolution d'une instance de Coloration sur Listes. Nous nous intéressons ensuite à la liste-colorabilité des graphes bipartis.
The raising of all-optical networks makes several theoretical algorithmic problems appear or reappear among which we can find : Load Minimization, Path Coloring, All-Optical Routing and List Coloring. The first three problems are NP-hard in general. We show more precisely that Path Coloring in meshes and toroidal meshes is No-APX. We also show that these problems can be solved by approximation algorithms if instances are reduced to mesh networks or toroidal mesh networks and if the paths we are looking for have row-column type. The List Coloring is a NP-complete problem in general. This is a variation and a generalization of the well-known vertex coloring problem. First, we study if knowing a classic coloring of a graph helps to solve an instance of List Coloring. Then we focus on bipartite graph choosability. | | Directeur(s) de thèse : | KONIG J.C. | | Co-directeur(s) de thèse : | COGIS O. | | Président du jury : | CHEIN M. | | Rapporteur(s) : | GERMA A.;BARTH D. | | Date de soutenance : | 19/12/2002 |
|
Affiner la recherche Interroger des sources externesProblèmes Algorithmiques dans les Réseaux Tout-Optique / J. PALAYSI
