No description available.

No description available.

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.

Dans une perspective de meilleure évaluation des pratiques de mobilité quotidienne, il convient de recentrer les méthodes et les outils d’aide à la décision autour des acteurs des déplacements : les usagers. Dans cette logique le modèle MICROBILIS a été développé afin d’évaluer l’adaptation des stratégies des usagers par rapport à leur environnement des transports. Trois champs sont mobilisés : les modèles de micro-simulation d’affectation, la théorie des graphes et les systèmes multi-agents. L’environnement est modélisé à partir d’un modèle microscopique des déplacements et d’un graphe cellulaire, définissant la capacité du réseau. Les simulations permettent de retrouver les relations empiriques de la dynamique de trafic sur les sections et mettent en évidence des contraintes supérieures de capacité au niveau des carrefours. Le passage à la simulation d’un réseau de grande taille induit la complexification de l’environnement et la multiplication des cas particuliers. Il n’a pas été possible de réaliser ce passage sans réduire les hypothèses initiales, devenant ainsi non représentatives de la réalité. / From the perspective of best practice assessment of daily mobility, it should refocus the methods and tools for decision aid around the actors in travel: users. In this logic MICROBILIS model was developed to evaluate the adaptation strategies of users relative to their environmental transport. Three streams have been mobilized: the micro-simulation of assignment models, graph theory and multi-agent systems. The environment is modeled from a microscopic simulator of movements and a cellular graph, defining the network capacity. The simulations allow to find the empirical relationships of the dynamics of traffic on the sections and highlight upper capacity constraints at intersections. The transition to the simulation of a large network induces the complexity of the environment and the multiplication of particular cases. It was not possible to make this transition without reducing the initial assumptions, making it unrepresentative of reality.

Les systèmes distribués modernes à large-échelle évoluent dans des contextes variables soumis à de nombreux aléas auxquels ils doivent s'adapter dynamiquement. Dans ce cadre, l'informatique autonome se propose de réduire les interventions humaines lentes et coûteuses, en leur préférant l'auto-gestion. Elle repose avant tout sur une description adéquate de ses composants, de leurs interactions et des différents aspects ou topologies qu'il peut adopter. Diverses approches de modélisation ont étés proposées dans la littérature, se concentrant en général sur certains du système dynamique et ne permettent ainsi pas de répondre à chacune des problématiques inhérentes à l'auto-gestion. Cette thèse traite de la modélisation basée graphes des systèmes dynamiques et de son adéquation pour la mise en œuvre des quatre propriétés fondamentales de l'informatique. Elle propose quatre principales contributions théoriques et appliquées. La première est une méthodologie pour la construction et la caractérisation générative de transformations correctes par construction dont l'application préserve nécessairement la correction du système. La seconde contribution consiste en une extension des systèmes de réécriture de graphe permettant de représenter, mettre à jour, évaluer et paramétrer les caractéristiques d'un système aisément et efficacement. Une étude expérimentale extensive révèle un net gain d'efficacité vis à vis de méthodes classiques. Les deux dernières contributions s'articulent autour de l'élaboration de deux modules de gestions visant : (1) des requêtes de traitement d'événements complexes et (2) tout système Machine-à-Machine se conformant au standard ETSI M2M. / Modern, large-scale systems are deployed in changing environments. They must dynamically adapt to context changes. In this scope, autonomic computing aims at reducing slow and costly human interventions, by building self-managed systems. Self-adaptability of a system is primarily based on a suitable description of its components, their interactions and the various states it can adopt. Various modeling approaches have been elaborated. They usually focus on some aspects or properties of dynamic systems and do not tackle each of self-management's requirements. This manuscript deals with graph-based representations of dynamic systems and their suitability for the implementation of autonomic computing's four fundamental properties : self-optimization, self-protection, self-healing and self-configuring. This thesis offers four principal theoretical and applied contributions. The first one is a methodology for the construction and generative characterization of transformations correct by construction whose application necessarily preserves a system's correctness. The second one consists in an extension of graph rewriting systems allowing to easily and efficiently represent, update, evaluate and configure a system's characteristics. An experimental study reveals a significant efficiency gain with regard to classical methods. The two lasts contribution are articulated around the design of two autonomic managers driving: (1) complex events processing requests and (2) any Machine-to-Machine system complying to the ETSI M2M2 standard.

Les principaux sujets étudiés dans cette thèse concernent le développement d'algorithmes stochastiques d'optimisation sous incertitude, l'étude de leurs propriétés théoriques et leurs applications. Les algorithmes proposés sont des variantes du recuit simulé qui n'utilisent que des estimations sans biais de la fonction de coût. On étudie leur convergence en utilisant des outils développés dans la théorie des processus de Markov : on utilise les propriétés du générateur infinitésimal et des inégalités fonctionnelles pour mesurer la distance entre leur distribution et une distribution cible. La première partie est dédiée aux graphes quantiques, munis d'une mesure de probabilité sur l'ensemble des sommets. Les graphes quantiques sont des versions continues de graphes pondérés non-orientés. Le point de départ de cette thèse a été de trouver la moyenne de Fréchet de tels graphes. La moyenne de Fréchet est une extension aux espaces métriques de la moyenne euclidienne et est définie comme étant le point qui minimise la somme des carrés des distances pondérées à tous les sommets. Notre méthode est basée sur une formulation de Langevin d'un recuit simulé bruité et utilise une technique d'homogénéisation. Dans le but d'établir la convergence en probabilité du processus, on étudie l'évolution de l'entropie relative de sa loi par rapport a une mesure de Gibbs bien choisie. En utilisant des inégalités fonctionnelles (Poincaré et Sobolev) et le lemme de Gronwall, on montre ensuite que l'entropie relative tend vers zéro. Notre méthode est testée sur des données réelles et nous proposons une méthode heuristique pour adapter l'algorithme à de très grands graphes, en utilisant un clustering préliminaire. Dans le même cadre, on introduit une définition d'analyse en composantes principales pour un graphe quantique. Ceci implique, une fois de plus, un problème d'optimisation stochastique, cette fois-ci sur l'espace des géodésiques du graphe. Nous présentons un algorithme pour trouver la première composante principale et conjecturons la convergence du processus de Markov associé vers l'ensemble voulu. Dans une deuxième partie, on propose une version modifiée de l'algorithme du recuit simulé pour résoudre un problème d'optimisation stochastique global sur un espace d'états fini. Notre approche est inspirée du domaine général des méthodes Monte-Carlo et repose sur une chaine de Markov dont la probabilité de transition à chaque étape est définie à l'aide de " mini-lots " de taille croissante (aléatoire). On montre la convergence en probabilité de l'algorithme vers l'ensemble optimal, on donne la vitesse de convergence et un choix de paramètres optimisés pour assurer un nombre minimal d'évaluations pour une précision donnée et un intervalle de confiance proche de 1. Ce travail est complété par un ensemble de simulations numériques qui illustrent la performance pratique de notre algorithme à la fois sur des fonctions tests et sur des données réelles issues de cas concrets. / The main topics of this thesis involve the development of stochastic algorithms for optimization under uncertainty, the study of their theoretical properties and applications. The proposed algorithms are modified versions of simulated an- nealing that use only unbiased estimators of the cost function. We study their convergence using the tools developed in the theory of Markov processes: we use properties of infinitesimal generators and functional inequalities to measure the distance between their probability law and a target one. The first part is concerned with quantum graphs endowed with a probability measure on their vertex set. Quantum graphs are continuous versions of undirected weighted graphs. The starting point of the present work was the question of finding Fréchet means on such a graph. The Fréchet mean is an extension of the Euclidean mean to general metric spaces and is defined as an element that minimizes the sum of weighted square distances to all vertices. Our method relies on a Langevin formulation of a noisy simulated annealing dealt with using homogenization. In order to establish the convergence in probability of the process, we study the evolution of the relative entropy of its law with respect to a convenient Gibbs measure. Using functional inequalities (Poincare and Sobolev) and Gronwall's Lemma, we then show that the relative entropy goes to zero. We test our method on some real data sets and propose an heuristic method to adapt the algorithm to huge graphs, using a preliminary clustering. In the same framework, we introduce a definition of principal component analysis for quantum graphs. This implies, once more, a stochastic optimization problem, this time on the space of the graph's geodesics. We suggest an algorithm for finding the first principal component and conjecture the convergence of the associated Markov process to the wanted set. On the second part, we propose a modified version of the simulated annealing algorithm for solving a stochastic global optimization problem on a finite space. Our approach is inspired by the general field of Monte Carlo methods and relies on a Markov chain whose probability transition at each step is defined with the help of mini batches of increasing (random) size. We prove the algorithm's convergence in probability towards the optimal set, provide convergence rate and its optimized parametrization to ensure a minimal number of evaluations for a given accuracy and a confidence level close to 1. This work is completed with a set of numerical experiments and the assessment of the practical performance both on benchmark test cases and on real world examples.

La problèmatique dont nous nous occupons dans cette thèse est la classification automatique d'images bidimensionnelles, ainsi que la détection d'objets génériques dans des images. Les avancées de ce champ de recherche contribuent à l'élaboration de systèmes intelligents, tels que des robots autonomes et la création d'un web sémantique. Dans ce contexte, la conception de représentations d'images et de classificateurs appropriés constituent des problèmes ambitieux. Notre travail de recherche fournit des solutions à ces deux problèmes, que sont la représentation et la classification d'images. Afin de générer notre représentation d'image, nous extrayons des attributs visuels de l'image et construisons une structure de graphe basée sur les propriétés liées au relations de proximités entre les points d'intérêt associés. Nous montrons que certaines propriétés spectrales de ces graphes constituent de bons invariants aux classes de transformations géométriques rigides. Notre représentation d'image est basée sur ces propriétés. Les résultats expérimentaux démontrent que cette représentation constitue une amélioration par rapport à d'autres représentations similaires, mais qui n'intègrent pas les informations liées à l'organisation spatiale des points d'intérêt. Cependant, un inconvénient de cette méthode est qu'elle fait appel à une quantification (avec pertes) de l'espace des attributs visuels afin d'être combinée avec un classificateur Support Vecteur Machine (SVM) efficace. Nous résolvons ce problème en créant un nouveau classificateur, basé sur la distance au plus proche voisin, et qui permet la classification d'objets assimilés à des ensembles de points. La linéarité de ce classificateur nous permet également de faire de la détection d'objet, en plus de la classification d'images. Une autre propriété intéressante de ce classificateur est sa capacité à combiner différents types d'attributs visuels de manière optimale. Nous utilisons cette propriété pour formuler le problème de classification de graphes de manière différente. Les expériences, menées sur une grande variété de jeux de données, montrent les bénéfices quantitatifs de notre approche. / We are concerned in this thesis by the problem of automated 2D image classification and general object detection. Advances in this field of research contribute to the elaboration of intelligent systems such as, but not limited to, autonomous robots and the semantic web. In this context, designing adequate image representations and classifiers for these representations constitute challenging issues. Our work provides innovative solutions to both these problems: image representation and classification. In order to generate our image representation, we extract visual features from the image and build a graphical structure based on properties of spatial proximity between the feature points. We show that certain spectral properties of this graph constitute good invariants to rigid geometric transforms. Our representation is based on these invariant properties. Experiments show that this representation constitutes an improvement over other similar representations that do not integrate the spatial layout of visual features. However, a drawback of this method is that it requires a lossy quantisation of the visual feature space in order to be combined with a state-of-the-art support vector machine (SVM) classifier. We address this issue by designing a new classifier. This generic classifier relies on a nearest-neighbour distance to classify objects that can be assimilated to feature sets, i.e: point clouds. The linearity of this classifier allows us to perform object detection, in addition to image classification. Another interesting property is its ability to combine different types of visual features in an optimal manner. We take advantage of this property to produce a new formulation for the classification of visual feature graphs. Experiments are conducted on a wide variety of publicly available datasets to justify the benefits of our approach.

Un fasciagraphe de taille n et de fibre F est constitué de n copies consécutives du graphe F, chaque copie étant reliée à la suivante selon le même schéma. Les rotagraphes sont définis similairement, mais selon une structure circulaire. Dans cette thèse nous caractérisons un ensemble de problèmes combinatoires qui peuvent être résolus de façon efficace dans la classe des fasciagraphes et rotagraphes. Dans ce contexte, nous définissons les (d,q,w)-propriétés closes et stables, et présentons pour de telles propriétés un algorithme pour calculer une solution optimale en temps constant pour l'ensemble des fasciagraphes ou rotagraphes de fibre fixée. Nous montrons que plusieurs problèmes communément étudiés dans la théorie des graphes et NP-complets dans le cas général sont caractérisés par des (d,q,w)-propriétés closes ou stables. Dans une seconde partie de la thèse, nous adaptons cet algorithme générique à trois problèmes spécifiques caractérisés par des (d,q,w)-propriétés stables : le problème du code identifiant minimum, et deux problèmes proches, celui de dominant-localisateur minimum et celui du dominant-total-localisateur minimum. Nous présentons alors une implémentation de l'algorithme qui nous a permis de répondre à des questions ouvertes dans certains rotagraphes particuliers : les bandes circulaires de hauteur bornée. Nous en déduisons d'autres résultats sur les bandes infinies de hauteur bornée. Enfin, nous explorons le problème du code identifiant dans une autre classe de graphes à structure répétitive : les graphes fractals de cycle. / A fasciagraph of length n and of fiber F, is constituted of n consecutive copies of a graph F, each copy being linked to the next one according to a same scheme. Rotagraphs are defines similarily, but along a circular structure. In this thesis, we caracterize a set of combinatorial problems that can be efficiently solved when applied on the class of rotagraphs and fasciagraphs. In this context, we define closed and stable (d,q,w)-properties, and we present, for such properties, an algorithm to compute an optimal solution, in constant time, for the set of fasciagraphs or rotagraphs of fixed fiber. We show that several problems, largely studied in graph theory, are caracterized by closed or stable (d,q,w)-properties. In a second part of the thesis, we adapt the generic algorithm to three problems caracterized by stable (d,q,w)-properties : the problem of minimum indentifying code, and two other, close to this one, the problem of minimum locating-dominating set et the one of minimum locating-total-dominating set. We present an implementation of our algorithm which has let us respond to open questions in a certain sub-class of rotagraphs : the circular strips of bounded height. We deduce from there other results on infinite strips of bounded height. Finaly we explore the problem of minimum identifying code in another class of graphs with repetitive structure : the fractal graphs.

La délimitation précise du contour des lésions pigmentées sur des images est une première étape importante pour le diagnostic assisté par ordinateur du mélanome. Cette thèse présente une nouvelle approche de la détection automatique du contour des lésions pigmentaires sur des images couleurs ou multispectrales de la peau. Nous présentons d'abord la notion de minimisation d'énergie par coupes de graphes en terme de Maxima A-Posteriori d'un champ de Markov. Après un rapide état de l'art, nous étudions l'influence des paramètres de l'algorithme sur les contours d'images couleurs. Dans ce cadre, nous proposons une fonction d'énergie basée sur des classifieurs performants (Machines à support de vecteurs et Forêts aléatoires) et sur un vecteur de caractéristiques calculé sur un voisinage local. Pour la segmentation de mélanomes, nous estimons une carte de concentration des chromophores de la peau, indices discriminants du mélanomes, à partir d'images couleurs ou multispectrales, et intégrons ces caractéristiques au vecteur. Enfin, nous détaillons le schéma global de la segmentation automatique de mélanomes, comportant une étape de sélection automatique des "graines" utiles à la coupure de graphes ainsi que la sélection des caractéristiques discriminantes. Cet outil est comparé favorablement aux méthodes classiques à base de coupure de graphes en terme de précision et de robustesse. / Accurate border delineation of pigmented skin lesion (PSL) images is a vital first step in computer-aided diagnosis (CAD) of melanoma. This thesis presents a novel approach of automatic PSL border detection on color and multispectral skin images. We first introduce the concept of energy minimization by graph cuts in terms of maximum a posteriori estimation of a Markov random field (MAP-MRF framework). After a brief state of the art in interactive graph-cut based segmentation methods, we study the influence of parameters of the segmentation algorithm on color images. Under this framework, we propose an energy function based on efficient classifiers (support vector machines and random forests) and a feature vector calculated on a local neighborhood. For the segmentation of melanoma, we estimate the concentration maps of skin chromophores, discriminating indices of melanomas from color and multispectral images, and integrate these features in a vector. Finally, we detail an global framework of automatic segmentation of melanoma, which comprises two main stages: automatic selection of "seeds" useful for graph cuts and the selection of discriminating features. This tool is compared favorably to classic graph-cut based segmentation methods in terms of accuracy and robustness.

Prédire la diffusion de l'information dans les réseaux sociaux est une tâche difficile qui peut cependant permettre de répondre à des problèmes intéressants : recommandation d'information, choix des meilleurs points d'entrée pour une diffusion, etc. La plupart des modèles proposés récemment sont des extensions des modèles à cascades et de seuil. Dans ces modèles, le processus de diffusion est basé sur les interactions entre les utilisateurs du réseau (la pression sociale), et ignore des caractéristiques importantes comme le contenu de l'information diffusé ou le rôle actif/passif des utilisateurs. Nous proposons une nouvelle famille de modèles pour prédire la façon dont le contenu se diffuse dans un réseau en prenant en compte ces nouvelles caractéristiques : le contenu diffusé, le profil des utilisateurs et leur tendance à diffuser. Nous montrons comment combiner ces caractéristiques et proposons une modélisation probabiliste pour résoudre le problème de la diffusion. Ces modèles sont illustrés et comparés avec d'autres approches sur deux jeux de données de blogs. Les résultats obtenus sur ces jeux de données montrent que prendre en compte ces caractéristiques est important pour modéliser le processus de diffusion. Enfin, nous étudions le problème de maximisation de l'influence avec ces modèles et prouvons qu'il est NP-difficile, avant de proposer une adaptation d'un algorithme glouton pour approcher la solution optimale. / Predicting the diffusion of information in social networks is a key problem for applications like Opinion Leader Detection, Buzz Detection or Viral Marketing. Many recent diffusion models are direct extensions of the Cascade and Threshold models, initially proposed for epidemiology and social studies. In such models, the diffusion process is based on the dynamics of interactions between neighbor nodes in the network (the social pressure), and largely ignores important dimensions as the content diffused and the active/passive role users tend to have in social networks. We propose here a new family of models that aims at predicting how a content diffuses in a network by making use of additional dimensions : the content diffused, user's profile and willingness to diffuse. In particular, we show how to integrate these dimensions into simple feature functions, and propose a probabilistic modeling to account for the diffusion process. These models are then illustrated and compared with other approaches on two blog datasets. The experimental results obtained on these datasets show that taking into account these dimensions are important to accurately model the diffusion process. Lastly, we study the influence maximization problem with these models and prove that it is NP-hard, prior to propose an adaptation of the greedy algorithm to approximate the optimal solution.