• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 6
  • 1
  • 1
  • Tagged with
  • 8
  • 8
  • 5
  • 4
  • 3
  • 3
  • 3
  • 3
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Décompositions de graphes : quelques limites et obstructions / Graphs decompositions : some limits and obstructions

Chapelle, Mathieu 05 December 2011 (has links)
Les décompositions de graphes, lorsqu’elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d’obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d’obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O(ntw+4). La seconde partie de notre travail porte sur l’étude du problème ENSEMBLE [σ, ρ]-DOMINANT, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d’entiers σ et ρ. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas ou le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l’est pas toujours, et que pour certains cas d’ensembles σ et ρ, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d’un nouveau problème de coloration appelé k-COLORATION ADDITIVE, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k ≥ 4 fixé, tandis qu’il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé. / Graphs decompositions of small width are usually used to solve efficiently problems which are difficult in general. In this thesis, we focus on some limits of these decompositions, and the construction of some obstructions certifying a large width. First, we give a generic algorithm unifying obstructions’ construction for several graph widths, in XP time when parameterized by the considered width. In particular, it gives the first algorithm computing efficiently an obstruction to tree-width in time O(ntw+4). Secondly, we study the parameterized complexity of [σ, ρ]-DOMINATING SET, a generalization of some domination problems characterized by two sets of integers σ and ρ. All known studies focused only on cases where this problem is FPT when parameterized by tree-width. In this work, we show that there are some cases where the problem is no longer FPT, and become W[1]-hard instead. Finally, we study the computational complexity of a new coloration problem, named k-ADDITIVE COLORING, which combines both graph theory and number theory. We show that this new problem is NP-complete for any fixed number k ≥ 4, while it can be solved in polynomial time on trees for any k.
2

Jeux de poursuite-évasion, décompositions et convexité dans les graphes

Pardo Soares, Ronan 08 November 2013 (has links) (PDF)
Cette thèse porte sur l'étude des propriétés structurelles de graphes dont la compréhension permet de concevoir des algorithmes efficaces pour résoudre des problèmes d'optimisation. Nous nous intéressons plus particulièrement aux méthodes de décomposition des graphes, aux jeux de poursuites et à la notion de convexité. Le jeu de Processus a été défini comme un modèle de la reconfiguration de routage. Souvent, ces jeux où une équipe de chercheurs doit effacer un graphe non orienté sont reliés aux décompositions de graphes. Dans les digraphes, nous montrons que le jeu de Processus est monotone et nous définissons une nouvelle décomposition de graphes que lui est équivalente. Ensuite, nous étudions d'autres décompositions de graphes. Nous proposons un algorithme FPT-unifiée pour calculer plusieurs paramètres de largeur de graphes. En particulier, ceci est le premier FPT-algorithme pour la largeur arborescente q-branché et spéciale d'un graphe. Nous étudions ensuite un autre jeu qui modélise les problèmes de pré-chargement. Nous introduisons la variante en ligne du jeu de surveillance. Nous étudions l'écart entre le jeu de surveillance classique et ses versions connecté et en ligne, en fournissant de nouvelles bornes. Nous définissons ensuite un cadre général pour l'étude des jeux poursuite-évasion. Cette méthode nous permet de donner les premiers résultats d'approximation pour certains de ces jeux. Finalement, nous étudions un autre paramètre lié à la convexité des graphes et à la propagation d'infection dans les réseaux, le nombre enveloppe. Nous fournissons plusieurs résultats de complexité en fonction des structures des graphes et en utilisant des décompositions de graphes.
3

Jeux de poursuite-évasion, décompositions et convexité dans les graphes / Pursuit-evasion, decompositions and convexity on graphs

Pardo Soares, Ronan 08 November 2013 (has links)
Cette thèse porte sur l’étude des propriétés structurelles de graphes dont la compréhension permet de concevoir des algorithmes efficaces pour résoudre des problèmes d’optimisation. Nous nous intéressons plus particulièrement aux méthodes de décomposition des graphes, aux jeux de poursuites et à la notion de convexité. Le jeu de Processus a été défini comme un modèle de la reconfiguration de routage. Souvent, ces jeux où une équipe de chercheurs doit effacer un graphe non orienté sont reliés aux décompositions de graphes. Dans les digraphes, nous montrons que le jeu de Processus est monotone et nous définissons une nouvelle décomposition de graphes que lui est équivalente. Ensuite, nous étudions d’autres décompositions de graphes. Nous proposons un algorithme FPT-unifiée pour calculer plusieurs paramètres de largeur de graphes. En particulier, ceci est le premier FPT-algorithme pour la largeur arborescente q-branché et spéciale d’un graphe. Nous étudions ensuite un autre jeu qui modélise les problèmes de pré-chargement. Nous introduisons la variante en ligne du jeu de surveillance. Nous étudions l’écart entre le jeu de surveillance classique et ses versions connecté et en ligne, en fournissant de nouvelles bornes. Nous définissons ensuite un cadre général pour l’étude des jeux poursuite-évasion. Cette méthode nous permet de donner les premiers résultats d’approximation pour certains de ces jeux. Finalement, nous étudions un autre paramètre lié à la convexité des graphes et à la propagation d’infection dans les réseaux, le nombre enveloppe. Nous fournissons plusieurs résultats de complexité en fonction des structures des graphes et en utilisant des décompositions de graphes. / This thesis focuses on the study of structural properties of graphs whose understanding enables the design of efficient algorithms for solving optimization problems. We are particularly interested in methods of decomposition, pursuit-evasion games and the notion of convexity. The Process game has been defined as a model for the routing reconfiguration problem in WDM networks. Often, such games where a team of searchers have to clear an undirected graph are closely related to graph decompositions. In digraphs, we show that the Process game is monotone and we define a new equivalent digraph decomposition. Then, we further investigate graph decompositions. We propose a unified FPT-algorithm to compute several graph width parameters. This algorithm turns to be the first FPT-algorithm for the special and the q-branched tree-width of a graph. We then study another pursuit-evasion game which models prefetching problems. We introduce the more realistic online variant of the Surveillance game. We investigate the gap between the classical Surveillance Game and its connected and online versions by providing new bounds. We then define a general framework for studying pursuit-evasion games, based on linear programming techniques. This method allows us to give first approximation results for some of these games. Finally, we study another parameter related to graph convexity and to the spreading of infection in networks, namely the hull number. We provide several complexity results depending on the graph structures making use of graph decompositions. Some of these results answer open questions of the literature.
4

Structurations de Graphes: Quelques Applications Algorithmiques

Kanté, Mamadou Moustapha 03 December 2008 (has links) (PDF)
Tous les problèmes définissables en \emph{logique monadique du second ordre } peuvent être résolus en temps polynomial dans les classes de graphes qui ont une \emph{largeur de clique} bornée. La largeur de clique est un paramètre de graphe défini de manière algébrique, c'est-à-dire, à partir d'opérations de composition de graphes. La \emph{largeur de rang}, définie de manière combinatoire, est une notion équivalente à la largeur de clique des graphes non orientés. Nous donnons une caractérisation algébrique de la largeur de rang et nous montrons qu'elle est linéairement bornée par la largeur arborescente. Nous proposons également une notion de largeur de rang pour les graphes orientés et une relation de \emph{vertex-minor} pour les graphes orientés. Nous montrons que les graphes orientés qui ont une largeur de rang bornée sont caractérisés par une liste finie de graphes orientés à exclure.<br>Beaucoup de classes de graphes n'ont pas une largeur de rang bornée, par exemple, les graphes planaires. Nous nous intéressons aux systèmes d'étiquetage dans ces classes de graphes. Un système d'étiquetage pour une propriété $P$ dans un graphe $G$, consiste à assigner une étiquette, aussi petite que possible, à chaque sommet de telle sorte que l'on puisse vérifier si $G$ satisfait $P$ en n'utilisant que les étiquettes des sommets. Nous montrons que si $P$ est une propriété définissable en \emph{logique du premier ordre} alors, certaines classes de graphes de \emph{largeur de clique localement bornée} admettent un système d'étiquetage pour $P$ avec des étiquettes de taille logarithmique. Parmi ces classes on peut citer les classes de graphes de degré borné, les graphes planaires et plus généralement les classes de graphes qui excluent un apex comme mineur et, les graphes d'intervalle unitaire.<br>Si $x$ et $y$ sont deux sommets, $X$ un ensemble de sommets et $F$ un ensemble d'arêtes, nous notons $Conn(x,y,X,F)$ la propriété qui vérifie dans un graphe donné si $x$ et $y$ sont connectés par un chemin, qui ne passe par aucun sommet de $X$ ni aucune arête de $F$. Cette propriété n'est pas définissable en logique du premier ordre. Nous montrons qu'elle admet un système d'étiquetage avec des étiquettes de taille logarithmique dans les graphes planaires. Nous montrons enfin que $Conn(x,y,X,\emptyset)$ admet également un système d'étiquetage avec des étiquettes de taille logarithmique dans des classes de graphes qui sont définies comme des \emph{combinaisons} de graphes qui ont une petite largeur de clique et telle que le graphe d'intersection de ces derniers est planaire et est de degré borné.
5

Inexact graph matching : application to 2D and 3D Pattern Recognition / Appariement inexact de graphes : application à la reconnaissance de formes 2D et 3D

Madi, Kamel 13 December 2016 (has links)
Les Graphes sont des structures mathématiques puissantes constituant un outil de modélisation universel utilisé dans différents domaines de l'informatique, notamment dans le domaine de la reconnaissance de formes. L'appariement de graphes est l'opération principale dans le processus de la reconnaissance de formes à base de graphes. Dans ce contexte, trouver des solutions d'appariement de graphes, garantissant l'optimalité en termes de précision et de temps de calcul est un problème de recherche difficile et d'actualité. Dans cette thèse, nous nous intéressons à la résolution de ce problème dans deux domaines : la reconnaissance de formes 2D et 3D. Premièrement, nous considérons le problème d'appariement de graphes géométriques et ses applications sur la reconnaissance de formes 2D. Dance cette première partie, la reconnaissance des Kites (structures archéologiques) est l'application principale considérée. Nous proposons un "framework" complet basé sur les graphes pour la reconnaissance des Kites dans des images satellites. Dans ce contexte, nous proposons deux contributions. La première est la proposition d'un processus automatique d'extraction et de transformation de Kites a partir d'images réelles en graphes et un processus de génération aléatoire de graphes de Kites synthétiques. En utilisant ces deux processus, nous avons généré un benchmark de graphes de Kites (réels et synthétiques) structuré en 3 niveaux de bruit. La deuxième contribution de cette première partie, est la proposition d'un nouvel algorithme d'appariement pour les graphes géométriques et par conséquent pour les Kites. L'approche proposée combine les invariants de graphes au calcul de l'édition de distance géométrique. Deuxièmement, nous considérons le problème de reconnaissance des formes 3D ou nous nous intéressons à la reconnaissance d'objets déformables représentés par des graphes c.à.d. des tessellations de triangles. Nous proposons une décomposition des tessellations de triangles en un ensemble de sous structures que nous appelons triangle-étoiles. En se basant sur cette décomposition, nous proposons un nouvel algorithme d'appariement de graphes pour mesurer la distance entre les tessellations de triangles. L'algorithme proposé assure un nombre minimum de structures disjointes, offre une meilleure mesure de similarité en couvrant un voisinage plus large et utilise un ensemble de descripteurs qui sont invariants ou au moins tolérants aux déformations les plus courantes. Finalement, nous proposons une approche plus générale de l'appariement de graphes. Cette approche est fondée sur une nouvelle formalisation basée sur le problème de mariage stable. L'approche proposée est optimale en terme de temps d'exécution, c.à.d. la complexité est quadratique O(n2), et flexible en terme d'applicabilité (2D et 3D). Cette approche se base sur une décomposition en sous structures suivie par un appariement de ces structures en utilisant l'algorithme de mariage stable. L'analyse de la complexité des algorithmes proposés et l'ensemble des expérimentations menées sur les bases de graphes des Kites (réelle et synthétique) et d'autres bases de données standards (2D et 3D) attestent l'efficacité, la haute performance et la précision des approches proposées et montrent qu'elles sont extensibles et générales / Graphs are powerful mathematical modeling tools used in various fields of computer science, in particular, in Pattern Recognition. Graph matching is the main operation in Pattern Recognition using graph-based approach. Finding solutions to the problem of graph matching that ensure optimality in terms of accuracy and time complexity is a difficult research challenge and a topical issue. In this thesis, we investigate the resolution of this problem in two fields: 2D and 3D Pattern Recognition. Firstly, we address the problem of geometric graphs matching and its applications on 2D Pattern Recognition. Kite (archaeological structures) recognition in satellite images is the main application considered in this first part. We present a complete graph based framework for Kite recognition on satellite images. We propose mainly two contributions. The first one is an automatic process transforming Kites from real images into graphs and a process of generating randomly synthetic Kite graphs. This allowing to construct a benchmark of Kite graphs (real and synthetic) structured in different level of deformations. The second contribution in this part, is the proposition of a new graph similarity measure adapted to geometric graphs and consequently for Kite graphs. The proposed approach combines graph invariants with a geometric graph edit distance computation. Secondly, we address the problem of deformable 3D objects recognition, represented by graphs, i.e., triangular tessellations. We propose a new decomposition of triangular tessellations into a set of substructures that we call triangle-stars. Based on this new decomposition, we propose a new algorithm of graph matching to measure the distance between triangular tessellations. The proposed algorithm offers a better measure by assuring a minimum number of triangle-stars covering a larger neighbourhood, and uses a set of descriptors which are invariant or at least oblivious under most common deformations. Finally, we propose a more general graph matching approach founded on a new formalization based on the stable marriage problem. The proposed approach is optimal in term of execution time, i.e. the time complexity is quadratic O(n2) and flexible in term of applicability (2D and 3D). The analyze of the time complexity of the proposed algorithms and the extensive experiments conducted on Kite graph data sets (real and synthetic) and standard data sets (2D and 3D) attest the effectiveness, the high performance and accuracy of the proposed approaches and show that the proposed approaches are extensible and quite general
6

Décompositions de graphes : quelques limites et obstructions

Chapelle, Mathieu 05 December 2011 (has links) (PDF)
Les décompositions de graphes, lorsqu'elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d'obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d'obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O^{tw+4}. La seconde partie de notre travail porte sur l'étude du problème Ensemble [Sigma,Rho]-Dominant, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d'entiers Sigma et Rho. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas où le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l'est pas toujours, et que pour certains cas d'ensembles Sigma et Rho, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d'un nouveau problème de coloration appelé k-Coloration Additive, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k >= 4 fixé, tandis qu'il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé.
7

Resource allocation in Cloud federation / Allocation et fédération des ressources informatiques dans le Cloud

Rebai, Salma 13 March 2017 (has links)
L'informatique en nuage (Cloud Computing) est un modèle à grande échelle et en évolution continue, permettant le provisionnement et l'utilisation des ressources informatiques à la demande, selon un modèle rentable de facturation à l'usage "pay-as-you-go". Ce nouveau paradigme a rapidement révolutionné l'industrie IT et a permis de nouvelles tendances en matière de prestation de services informatiques, y compris l'externalisation des infrastructures IT vers des prestataires tiers spécialisés. Cependant, la nature multi-utilisateur des plateformes d'hébergement, ainsi que la complexité des demandes, soulèvent plusieurs défis liés à la gestion des ressources Cloud. Malgré l'attention croissante portée à ce sujet, la plupart des efforts ont été axés sur des solutions centrées utilisateur, et malheureusement beaucoup moins sur les difficultés rencontrées par les fournisseurs pour maximiser leurs bénéfices. Dans ce contexte, la fédération de Cloud a été récemment proposée comme une solution clé pour répondre à l'augmentation et la fluctuation des charges de travail. Les fournisseurs ayant des besoins complémentaires en ressources au fil du temps, peuvent collaborer et partager leurs infrastructures respectives via l'externalisation ("Outsourcing") pour mieux satisfaire les demandes et exigences des utilisateurs. Cette thèse aborde le problème d'optimisation du profit via la fédération et l'allocation optimale des ressources parmi plusieurs fournisseurs d'infrastructures Cloud. L'étude examine les principaux défis et opportunités liés à la maximisation des revenus dans une fédération de Clouds, et définit des stratégies efficaces pour diriger les fournisseurs dans leurs décisions de coopération. Le but est de fournir des algorithmes qui automatisent la sélection du plan d'allocation le plus rentable, qui satisfait à la fois la demande des utilisateurs et les exigences de mise en réseau. Nous visons des modèles d'allocation génériques et robustes qui répondent aux nouvelles tendances Cloud, et de traiter les requêtes simples ainsi que complexes nécessitant le provisionnement de services composites avec différentes ressources distribuées et connectées. Conformément aux objectifs de la thèse, nous avons mené une étude approfondie des travaux antérieurs traitant la problématique de provisionnement des ressources d'infrastructure dans les environnements Cloud. L'analyse a porté notamment sur les modèles d'allocation ayant pour objectif la maximisation de profit et les lacunes et défis associés dans les fédérations de Clouds. Dans un deuxième temps, nous avons proposé un programme linéaire en nombre entiers (ILP), pour aider les fournisseurs de services dans leurs décisions de coopération via des actions optimales d'externalisation (outsourcing), d'internalisation (insourcing) et d'allocation en local. Ces différentes décisions d'allocation sont traitées conjointement dans une formule d'optimisation globale qui partitionne les graphes de requêtes entre les membres de la fédération, tout en satisfaisant les exigences de communication entre les services élémentaires. En plus de la topologie des graphes de ressources, ce partitionnement prend en compte les prix dynamiques et les quotas proposés par les membres de la fédération ainsi que les coûts d'hébergement des ressources et de leur mise en réseau. Enfin, nous avons proposé un algorithme heuristique pour améliorer les temps de convergence avec les instances de problèmes à grande échelle. L'approche proposée utilise un algorithme de "clustering" basé sur les arbres de Gomory-Hu pour le partitionnement des graphes et une stratégie de meilleur ajustement (Best-Fit matching) pour l'allocation et le placement des sous-graphes résultants. L'utilisation conjointe de ces deux techniques permet de capturer l'essence du problème d'optimisation et de respecter les différents objectifs fixés, tout en améliorant le temps de convergence vers les solutions quasi-optimales de plusieurs ordres de grandeur / Cloud computing is a steadily maturing large-scale model for providing on-demand IT resources on a pay-as-you-go basis. This emerging paradigm has rapidly revolutionized the IT industry and enabled new service delivery trends, including infrastructure externalization to large third-party providers. The Cloud multi-tenancy architecture raises several management challenges for all stakeholders. Despite the increasing attention on this topic, most efforts have been focused on user-centric solutions, and unfortunately much less on the difficulties encountered by Cloud providers in improving their business. In this context, Cloud Federation has been recently suggested as a key solution to the increasing and variable workloads. Providers having complementary resource requirements over time can collaborate and share their respective infrastructures, to dynamically adjust their hosting capacities in response to users' demands. However, joining a federation makes the resource allocation more complex, since providers have to also deal with cooperation decisions and workload distribution within the federation. This is of crucial importance for cloud providers from a profit standpoint and especially challenging in a federation involving multiple providers and distributed resources and applications. This thesis addresses profit optimization through federating and allocating resources amongst multiple infrastructure providers. The work investigates the key challenges and opportunities related to revenue maximization in Cloud federation, and defines efficient strategies to govern providers' cooperation decisions. The goal is to provide algorithms to automate the selection of cost-effective distributed allocation plans that simultaneously satisfy user demand and networking requirements. We seek generic and robust models able to meet the new trends in Cloud services and handle both simple and complex requests, ranging from standalone VMs to composite services requiring the provisioning of distributed and connected resources. In line with the thesis objectives, we first provide a survey of prior work on infrastructure resource provisioning in Cloud environments. The analysis mainly focuses on profit-driven allocation models in Cloud federations and the associated gaps and challenges with emphasis on pricing and networking issues. Then, we present a novel exact integer linear program (ILP), to assist IaaS providers in their cooperation decisions, through optimal "insourcing", "outsourcing" and local allocation operations. The different allocation decisions are treated jointly in a global optimization formulation that splits resource request graphs across federation members while satisfying communication requirements between request subsets. In addition to the request topology, this partitioning takes into account the dynamic prices and quotas proposed by federation members as well as the costs of resources and their networking. The algorithm performance evaluation and the identified benefits confirm the relevance of resource federation in improving providers' profits and shed light into the most favorable conditions to join or build a federation. Finally, a new topology-aware allocation heuristic is proposed to improve convergence times with large-scale problem instances. The proposed approach uses a Gomory-Hu tree based clustering algorithm for request graphs partitioning, and a Best-Fit matching strategy for subgraphs placement and allocation. Combining both techniques captures the essence of the optimization problem and meets the objectives, while speeding up convergence to near-optimal solutions by several orders of magnitude
8

Graph structurings : some algorithmic applications / Structurations des graphes : quelques applications algorithmiques

Kanté, Mamadou Moustapha 03 December 2008 (has links)
Tous les problèmes définissables en logique du second ordre monadique peuvent être résolus en temps polynomial dans les classes de graphes qui ont une largeur de clique bornée. La largeur de clique est un paramètre de graphe défini de manière algébrique, c'est-à-dire, à partir d'opérations de composition de graphes. La largeur de rang, définie de manière combinatoire, est une notion équivalente à la largeur de clique des graphes non orientés. Nous donnons une caractérisation algébrique de la largeur de rang et nous montrons qu'elle est linéairement bornée par la largeur arborescente. Nous proposons également une notion de largeur de rang pour les graphes orientés et une relation de vertex-minor pour les graphes orientés. Nous montrons que les graphes orientés qui ont une largeur de rang bornée sont caractérisés par une liste finie de graphes orientés à exclure comme vertex-minor. Beaucoup de classes de graphes n'ont pas une largeur de rang bornée, par exemple, les graphes planaires. Nous nous intéressons aux systèmes d'étiquetage dans ces classes de graphes. Un système d'étiquetage pour une propriété P dans un graphe G, consiste à assigner une étiquette, aussi petite que possible, à chaque sommet de telle sorte que l'on puisse vérifier si G satisfait P en n'utilisant que les étiquettes des sommets. Nous montrons que si P est une propriété définissable en logique du premier ordre alors, certaines classes de graphes de largeur de clique localement bornée admettent un système d'étiquetage pour P avec des étiquettes de taille logarithmique. Parmi ces classes on peut citer les classes de graphes de degré borné, les graphes planaires et plus généralement les classes de graphes qui excluent un apex comme mineur et, les graphes d'intervalle unitaire. Si x et y sont deux sommets, X un ensemble de sommets et F un ensemble d'arêtes, nous notons Conn(x,y,X,F) la propriété qui vérifie dans un graphe donné si x et y sont connectés par un chemin, qui ne passe par aucun sommet de X si aucune arête de F. Cette propriété n'est pas définissable en logique du premier ordre. Nous montrons qu'elle admet un système d'étiquetage avec des étiquettes de taille logarithmique dans les graphes planaires. Nous montrons enfin que Conn(x,y,X,0) admet également un système d'étiquetage avec des étiquettes de taille logarithmique dans des classes de graphes qui sont définies comme des combinaisons de graphes qui ont une petite largeur de clique et telles que le graphe d'intersection de ces derniers est planaire et est de degré borné. / Every property definable in onadic second order logic can be checked in polynomial-time on graph classes of bounded clique-width. Clique-width is a graph parameter defined in an algebraical way, i.e., with operations ``concatenating graphs'' and that generalize concatenation of words.Rank-width, defined in a combinatorial way, is equivalent to the clique-width of undirected graphs. We give an algebraic characterization of rank-width and we show that rank-width is linearly bounded in term of tree-width. We also propose a notion of ``rank-width'' of directed graphs and a vertex-minor inclusion for directed graphs. We show that directed graphs of bounded ``rank-width'' are characterized by a finite list of finite directed graphs to exclude as vertex-minor. Many graph classes do not have bounded rank-width, e.g., planar graphs. We are interested in labeling schemes on these graph classes. A labeling scheme for a property P in a graph G consists in assigning a label, as short as possible, to each vertex of G and such that we can verify if G satisfies P by just looking at the labels. We show that every property definable in first order logic admit labeling schemes with labels of logarithmic size on certain graph classes that have bounded local clique-width. Bounded degree graph classes, minor closed classes of graphs that exclude an apex graph as a minor have bounded local clique-width. If x and y are two vertices and X is a subset of the set of vertices and Y is a subset of the set of edges, we let Conn(x,y,X,Y) be the graph property x and y are connected by a path that avoids the vertices in X and the edges in Y. This property is not definable by a first order formula. We show that it admits a labeling scheme with labels of logarithmic size on planar graphs. We also show that Conn(x,y,X,0) admits short labeling schemes with labels of logarithmic size on graph classes that are ``planar gluings'' of graphs of small clique-width and with limited overlaps.

Page generated in 0.5224 seconds