A partir de cette page vous pouvez :
| Retourner au premier écran avec les dernières notices... |
Résultat de la recherche
3 résultat(s) recherche sur le tag 'graphes'
Affiner la recherche Interroger des sources externesDécomposition Modulaire des Graphes, Théorie, Extensions et Algorithmes / F. DEMONTGOLFIER
Titre : Décomposition Modulaire des Graphes, Théorie, Extensions et Algorithmes Type de document : texte imprimé Auteurs : F. DEMONTGOLFIER, Auteur Année de publication : 2003 Langues : Français (fre) Tags : GRAPHES ALGORITHMES DECOMPOSITION MODULAIRE FAMILLES PARTITIVES 2-MODULES 2-JOINTS GRAPHES BIPARTIS GRAPHES D'INTERVALLES GRAPHES DE PERMUTATION MODULAR DECOMPOSITION OF GRAPHS. THEORY EXTENSIONS AND ALGORITHMS. GRAPHS ALGORITHMS MODULAR DECOMPOSITION PARTITIVE SET FAMILIES2-MODULES HOMOGENEOUS PAIRS 2-JOINS BIPARTITE GRAPHS INTERVAL GRAPHS PERMUTATION GRAPHS Index. décimale : THE Thèses de doctorat Résumé : La première partie de cette thèse théorique, concerne des familles de parties d'un ensemble possédant les même propriétés que les modules d'un graphes : les familles partitives. On s'intéresse à des généralisations de la décomposition modulaire des graphes. La famille des 2-modules est étudiée. Puis sont exposées les décompositions en 2-joints, en sesquimodules, et la décomposition bimodulaire des graphes bipartis, parallèle presque complet dans le cas biparti de la décomposition modulaire, qui se calcule polynômialement. Enfin la seconde partie, pratique, présente des algorithmes de décomposition modulaire en O(n+m) pour le cas des graphes non-orientés, des tournois, et des graphes orientés, et en O(n) pour les graphes d'intervalles et les graphes de permutation. Tous ces algorithmes sont linéaires en la taille de la donnée; les deux premiers sont plus simples que les algorithmes existants; et les trois derniers atteignent cette borne pour la première fois.
The first part of this thesis is devoted to theory. First it is question of set decompositions that have the same properties than modular decomposition: the partitive families. Then are presented some graph decompositions that extend modular decomposition, using the notion of 2-modules (homogeneous pairs). This is the case for the split decomposition of Cunningham, and also for the new 2-joins and sesquimodules decompositions. A analog of modules for bipartites graphs, the bimodules, leads to a decomposition theory very near the modular decomposition of directed graphs. The second part is practical and presents modular decompositions algorithms for undirected graphs, tournaments, directed graphs, interval graphs and permutation graphs. All these algorithms run in linear-time from the input: O(n+m) for the three first classes, O(n) for the two last classes. The tree last algorithms reach linearity for the first time.Directeur(s) de thèse : HABIB M. Co-directeur(s) de thèse : PAUL C. Président du jury : CROCHEMORE M. Rapporteur(s) : McCONNELL R.M.;VANHERPE J.M.;GAVOILLE C. Examinateur(s) : FOUQUET J.L. Date de soutenance : 05/12/2003 Décomposition Modulaire des Graphes, Théorie, Extensions et Algorithmes [texte imprimé] / F. DEMONTGOLFIER, Auteur . - 2003.
Langues : Français (fre)
Tags : GRAPHES ALGORITHMES DECOMPOSITION MODULAIRE FAMILLES PARTITIVES 2-MODULES 2-JOINTS GRAPHES BIPARTIS GRAPHES D'INTERVALLES GRAPHES DE PERMUTATION MODULAR DECOMPOSITION OF GRAPHS. THEORY EXTENSIONS AND ALGORITHMS. GRAPHS ALGORITHMS MODULAR DECOMPOSITION PARTITIVE SET FAMILIES2-MODULES HOMOGENEOUS PAIRS 2-JOINS BIPARTITE GRAPHS INTERVAL GRAPHS PERMUTATION GRAPHS Index. décimale : THE Thèses de doctorat Résumé : La première partie de cette thèse théorique, concerne des familles de parties d'un ensemble possédant les même propriétés que les modules d'un graphes : les familles partitives. On s'intéresse à des généralisations de la décomposition modulaire des graphes. La famille des 2-modules est étudiée. Puis sont exposées les décompositions en 2-joints, en sesquimodules, et la décomposition bimodulaire des graphes bipartis, parallèle presque complet dans le cas biparti de la décomposition modulaire, qui se calcule polynômialement. Enfin la seconde partie, pratique, présente des algorithmes de décomposition modulaire en O(n+m) pour le cas des graphes non-orientés, des tournois, et des graphes orientés, et en O(n) pour les graphes d'intervalles et les graphes de permutation. Tous ces algorithmes sont linéaires en la taille de la donnée; les deux premiers sont plus simples que les algorithmes existants; et les trois derniers atteignent cette borne pour la première fois.
The first part of this thesis is devoted to theory. First it is question of set decompositions that have the same properties than modular decomposition: the partitive families. Then are presented some graph decompositions that extend modular decomposition, using the notion of 2-modules (homogeneous pairs). This is the case for the split decomposition of Cunningham, and also for the new 2-joins and sesquimodules decompositions. A analog of modules for bipartites graphs, the bimodules, leads to a decomposition theory very near the modular decomposition of directed graphs. The second part is practical and presents modular decompositions algorithms for undirected graphs, tournaments, directed graphs, interval graphs and permutation graphs. All these algorithms run in linear-time from the input: O(n+m) for the three first classes, O(n) for the two last classes. The tree last algorithms reach linearity for the first time.Directeur(s) de thèse : HABIB M. Co-directeur(s) de thèse : PAUL C. Président du jury : CROCHEMORE M. Rapporteur(s) : McCONNELL R.M.;VANHERPE J.M.;GAVOILLE C. Examinateur(s) : FOUQUET J.L. Date de soutenance : 05/12/2003 Réservation
Réserver ce document
Exemplaires
Cote Support Localisation Section Notes Disponibilité THE-03 / 9924 Papier THESES INFORMATIQUE Disponible Documents numériques
Fichier (PDF)URL
Titre : Graphes du Web, Mesures d'Importance à la PageRank Type de document : texte imprimé Auteurs : F. MATHIEU, Auteur Année de publication : 2004 Langues : Français (fre) Tags : GRAPHES WEB ARBRE DE DECOMPOSITION MATRICES SOUS-STOCHASTIQUES PAGERANK ALGORITHMES RETOUR ARRIERE FLOTS D'IMPORTANCE GRAPHS WWW DECOMPOSITION TREE SUBSTOCHASTIC MATRIX PAGERANK RANDOM WALK ALGORITHMS BACKOFF PROCESS IMPORTANCE FLOWS Index. décimale : THE Thèses de doctorat Résumé : L'application des mesures d'importance de type PageRank aux graphes du Web est le sujet de cette thèse, qui est divisée en deux parties. La première introduit une famille particulière de grands graphes, les graphes du Web. Elle commence par définir la notion de Web indexable, puis donne quelques considérations sur les tailles des portions de Web effectivement indexées. Pour finir, elle donne et utilise quelques constatations sur les structures que l'on peut observer sur les graphes induits par ces portions de Web. Ensuite, la seconde partie étudie en profondeur les mesures d'importance à la PageRank. Après un rappel sur la théorie des chaînes de Markov est présentée une classification originale des algorithmes de PageRank, qui part du modèle le plus simple jusqu'à prendre en compte toutes les spécificités liées aux graphes du Web. Enfin, de nouveaux algorithmes sont proposés. L'algorithme BackRank utilise un modèle alternatif de parcours du graphe du Web pour un calcul de PageRank plus rapide. La structure fortement clusterisée des graphes du Web permet quant à elle de décomposer le PageRank sur les sites Web, ce qui est réalisé par les algorithmes FlowRank et BlowRank.
The purpose of this thesis is to apply PageRank-like measures to Web graphs. The first part introduces the Web graphs. First we define the notion of indexable Web, then we give an insight on how big the effective crawls really are. Finally, we notice and use some of the structures that exist on the portions of the Web known as Web graphs. Then, the second part study deeply the PageRank algorithms. After a remainder on Markov chains theory is given an original classification of PageRank algorithms. From a basic model, we incorporate all the specificities needed to cope with real Web graphs. Lastly, new algorithms are proposed. BackRank uses an alternative random surfer modeling leading to a faster computation. The highly clustered structure of Web graphs allows a PageRank decomposition according to Web sites, and is the reason for introducing the algorithms FlowRank and BlowRank.Directeur(s) de thèse : HABIB M. Co-directeur(s) de thèse : VIENNOT L. Président du jury : JEAN-MARIE A. Rapporteur(s) : ABITEBOUL S.;FRAIGNIAUD P. Examinateur(s) : BACELLI F. Invité(s) : BLONDEL V. Date de soutenance : 08/12/2004 Graphes du Web, Mesures d'Importance à la PageRank [texte imprimé] / F. MATHIEU, Auteur . - 2004.
Langues : Français (fre)
Tags : GRAPHES WEB ARBRE DE DECOMPOSITION MATRICES SOUS-STOCHASTIQUES PAGERANK ALGORITHMES RETOUR ARRIERE FLOTS D'IMPORTANCE GRAPHS WWW DECOMPOSITION TREE SUBSTOCHASTIC MATRIX PAGERANK RANDOM WALK ALGORITHMS BACKOFF PROCESS IMPORTANCE FLOWS Index. décimale : THE Thèses de doctorat Résumé : L'application des mesures d'importance de type PageRank aux graphes du Web est le sujet de cette thèse, qui est divisée en deux parties. La première introduit une famille particulière de grands graphes, les graphes du Web. Elle commence par définir la notion de Web indexable, puis donne quelques considérations sur les tailles des portions de Web effectivement indexées. Pour finir, elle donne et utilise quelques constatations sur les structures que l'on peut observer sur les graphes induits par ces portions de Web. Ensuite, la seconde partie étudie en profondeur les mesures d'importance à la PageRank. Après un rappel sur la théorie des chaînes de Markov est présentée une classification originale des algorithmes de PageRank, qui part du modèle le plus simple jusqu'à prendre en compte toutes les spécificités liées aux graphes du Web. Enfin, de nouveaux algorithmes sont proposés. L'algorithme BackRank utilise un modèle alternatif de parcours du graphe du Web pour un calcul de PageRank plus rapide. La structure fortement clusterisée des graphes du Web permet quant à elle de décomposer le PageRank sur les sites Web, ce qui est réalisé par les algorithmes FlowRank et BlowRank.
The purpose of this thesis is to apply PageRank-like measures to Web graphs. The first part introduces the Web graphs. First we define the notion of indexable Web, then we give an insight on how big the effective crawls really are. Finally, we notice and use some of the structures that exist on the portions of the Web known as Web graphs. Then, the second part study deeply the PageRank algorithms. After a remainder on Markov chains theory is given an original classification of PageRank algorithms. From a basic model, we incorporate all the specificities needed to cope with real Web graphs. Lastly, new algorithms are proposed. BackRank uses an alternative random surfer modeling leading to a faster computation. The highly clustered structure of Web graphs allows a PageRank decomposition according to Web sites, and is the reason for introducing the algorithms FlowRank and BlowRank.Directeur(s) de thèse : HABIB M. Co-directeur(s) de thèse : VIENNOT L. Président du jury : JEAN-MARIE A. Rapporteur(s) : ABITEBOUL S.;FRAIGNIAUD P. Examinateur(s) : BACELLI F. Invité(s) : BLONDEL V. Date de soutenance : 08/12/2004 Réservation
Réserver ce document
Exemplaires
Cote Support Localisation Section Notes Disponibilité THE-04 / 11639 Papier THESES INFORMATIQUE Disponible Documents numériques
Fichier (PDF)URL
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 Réservation
Réserver ce document
Exemplaires
Cote Support Localisation Section Notes Disponibilité THE-02 / 7478 Papier THESES INFORMATIQUE Disponible Documents numériques
Fichier (PDF)URL
