• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 19
  • 9
  • 3
  • Tagged with
  • 32
  • 12
  • 9
  • 9
  • 9
  • 7
  • 6
  • 6
  • 5
  • 5
  • 5
  • 5
  • 4
  • 4
  • 4
  • 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.
11

Estimation sur des bases orthogonales des propriétés thermiques de matériaux hétérogènes à propriétés constantes par morceaux

Godin, Alexandre 25 January 2013 (has links)
Ce travail se propose de caractériser thermiquement des composites à microstructures complexes. Il s’agit de développer des méthodes d’estimation permettant d’identifier les propriétés thermiques des différentes phases en présence, ainsi que celles associées à leurs interfaces, à partir de mesures issues de la thermographie infrarouge. Cette estimation paramétrique nécessite la connaissance au préalable de la structure géométrique de l’échantillon. Le premier objectif concerne donc l’identification de la structure de l’échantillon testé par la discrimination des différentes phases et interfaces. Une fois la structure de l’échantillon connue, le second objectif est l’identification des paramètres thermiques des différents constituants ainsi que ceux de leurs interfaces. On se propose d’exploiter deux tests spécifiques utilisant le même dispositif expérimental. Deux méthodes mathématiques différentes ont été développées et utilisées pour exploiter les mesures de champ issues du premier test et permettre de retrouver la microstructure de l’échantillon. La première est fondée sur la décomposition en valeurs singulières des données de températures recueillies. Il est montré que cette méthode permet d’obtenir des représentations de la microstructure de très bonne qualité à partir de mesures même fortement bruitées. La seconde méthode permet de raffiner les résultats obtenus à l’aide de la méthode précédente. Elle repose sur la résolution d’un problème d’optimisation sous contraintes en exploitant la technique dite Level-Set pour identifier les frontières des différents constituants de l’échantillon. L’étape d’identification des propriétés thermiques des constituants et des interfaces exploite les mesures de champs issues du second test expérimental. La méthode développée, la SVD-FT combine des techniques de décompositions en valeurs singulières avec desfonctions tests particulières pour dériver des estimateurs linéaires des propriétés recherchées.Cette méthode permet de limiter les effets du bruit de mesure sur la qualité de l’estimation et de s’affranchir des opérations de filtrage des données. / This work reports on the thermal characterization of composites with a complex microstructure. It aims at developping mathematical methods to identify the thermal properties of the constituants and thoses associate at their interfaces. The first step consistsin discriminating the microstructure of the sample to be tested. Then, when the sample structure is known, the second step consists in estimating the thermal parameters of the different phases and those at their interfaces. One experimental device has been set up to realize those two steps. Two mathematical methods have been developped and used to discriminate the microstructure based on the images of the sample recorded bu an infrared camera. The first method is based on the singular value decomposition of the temperature data. It has been shown that this method gives a very good representation of the microstructure even with very noisy data. The second method allows to refine the results obtained by the first one. This method is based on the resolution of an optimization problem under constraints and use a Level-Set technic to identify the boundary of each phase. To estimate the thermal properties of each phase and its interface, the infrared images of the second experiment have been used. The SVD-FT method developed in this work combines the singular values decomposition technic with particular tests functions to derive linear estimat or for the thermal properties. As a result, a significant amplification of the signal/noise ratios is reached.
12

Décompositions parcimonieuses : approches Bayésiennes et application à la compression d'image

Drémeau, Angélique 19 November 2010 (has links) (PDF)
Cette thèse s'intéresse à différentes techniques de compression d'image combinant à la fois des aspects Bayésiens et des aspects ”décompositions parcimonieuses”. Deux types de compression sont en particulier examinés. Le codage par transformation, d'abord, est traité sous l'angle de l'optimisation de la transformation. L'étude de bases prédéfinies puis apprises par un algorithme de la littérature constitue une introduction à la conception d'un nouvel algorithme d'apprentissage Bayésien, favorisant la parcimonie de la décomposition. Le codage prédictif ensuite est abordé. Inspiré de contributions récentes s'appuyant sur des décompositions parcimonieuses, un nouvel algorithme de prédiction Bayésien reposant sur un mélange de décompositions parcimonieuses est proposé. Enfin, ces travaux ont permis de mettre en évidence l'intérêt de structurer la parcimonie des décompositions. Par exemple, une pondération des atomes de la décomposition peut être envisagée via l'utilisation d'un modèle Bernoulli-Gaussien de paramètres différents. Ce modèle est considéré dans une dernière partie, pour le développement d'algorithmes de décompositions parcimonieuses.
13

Etude statistique du champ de pression à proximité des jets axisymétriques turbulents à haut nombre de Reynolds

Coiffet, Francois 13 December 2006 (has links) (PDF)
Le champ proche des jets est une zone où cohabitent des contributions de pression de nature hydrodynamique et acoustique. Leurs caractéristiques sont méconnues, conduisant à une définition controversée des frontières de cette région ainsi qu'à l'impossibilité d'y prédire les niveaux de pression effectivement rencontrés. Cette zone présente un fort intérêt pour l'étude de la dynamique du jet ainsi que pour celle du rôle que peuvent jouer les structures cohérentes dans les mécanismes de génération de bruit aéroacoustique. L'étude présentée ici porte sur un jet subsonique, de nombre de Mach Mj=0,3, et un jet supersonique, Mj=1,4. Elle s'appuie sur des mesures acoustiques en champs proche et lointain ainsi que des mesures de pression champ proche synchrones à des mesures de vitesse dans l'écoulement par vélocimétrie laser à effet Doppler (LDV). Une interaction forte entre les deux contributions de pression est mise en évidence par des pertes de cohérence importantes. Ce phénomène, dont un modèle est proposé, permet de définir précisément la frontière du champ proche par le produit du nombre d'onde et de la position radiale kr=1,3. L'analyse par décomposition orthogonale aux valeurs propres (POD), sur la base de laquelle est également proposée une méthode de normalisation des données, montre le caractère très cohérent du champ de pression proche à basse fréquence ainsi que l'importance de la prise en compte des contributions azimutales. Une séparation des contributions hydrodynamique et acoustique de pression est obtenue grâce à un filtrage POD. La champ de pression instantanée est déterminé sur une surface entourant le jet grâce à une extension au domaine spectral de l'estimation stochastique linéaire (LSE). Ces données sont utilisées pour estimer le rayonnement acoustique du jet par une formulation intégrale de Kirchhoff ainsi que pour extraire la structuration tridimensionnelle de l'écoulement.
14

Trigraphes de Berge apprivoisés / Tame Berge trigraphes

Trunck, Théophile 17 September 2014 (has links)
L'objectif de cette thèse est de réussir à utiliser des décompositions de graphes afin de résoudre des problèmes algorithmiques sur les graphes. Notre objet d'étude principal est la classe des graphes de Berge apprivoisés. Les graphes de Berge sont les graphes ne possédant ni cycle de longueur impaire supérieur à 4 ni complémentaire de cycle de longueur impaire supérieure à 4. Dans les années 60, Claude Berge a conjecturé que les graphes de Berge étaient des graphes parfaits. C'est-à-dire que la taille de la plus grande clique est exactement le nombre minimum de couleurs nécessaire à une coloration propre et ce pour tout sous-graphe. En 2002, Chudnovsky, Robertson, Seymour et Thomas ont démontré cette conjecture en utilisant un théorème de structure: les graphes de Berge sont basiques ou admettent une décomposition. Ce résultat est très utile pour faire des preuves par induction. Cependant, une des décompositions du théorème, la skew-partition équilibrée, est très difficile à utiliser algorithmiquement. Nous nous focalisons donc sur les graphes de Berge apprivoisés, c'est-à-dire les graphes de Berge sans skew-partition équilibrée. Pour pouvoir faire des inductions, nous devons adapter le théorème destructure de Chudnovsky et al à notre classe. Nous prouvons un résultat plus fort: les graphes de Berge apprivoisés sont basiques ou admettent une décomposition telle qu'un côté de la décomposition soit toujours basique. Nous avons de plus un algorithme calculant cette décomposition. Nous utilisons ensuite notre théorème pour montrer que les graphes de Berge apprivoisés admettent la propriété du grand biparti, de la clique-stable séparation et qu'il existe un algorithme polynomial permettant de calculer le stable maximum. / The goal of this these is to use graph's decompositions to solve algorithmic problems on graphs. We will study the class of Berge tame graphs. A Berge graph is a graph without cycle of odd length at least 4 nor complement of cycle of odd length at least 4.In the 60's, Claude Berge conjectured that Berge graphs are perfect graphs. The size of the biggest clique is exactly the number of colors required to color the graph. In 2002, Chudnovsky, Robertson, Seymour et Thomas proved this conjecture using a theorem of decomposition: Berge graphs are either basic or have a decomposition. This is a useful result to do proof by induction. Unfortunately, one of the decomposition, the skew-partition, is really hard to use. We arefocusing here on Berge tame graphs, i.e~Berge graph without balanced skew-partition. To be able to do induction, we must first adapt the Chudnovsky et al's theorem of structure to our class. We prove a stronger result: Berge tame graphs are basic or have a decomposition such that one side is always basic. We also have an algorithm to compute this decomposition. We then use our theorem to prouve that Berge tame graphs have the big-bipartite property, the clique-stable set separation property and there exists a polytime algorithm to compute the maximum stable set.
15

High Performance Parallel Algorithms for Tensor Decompositions / Algorithmes Parallèles pour les Décompositions des Tenseurs

Kaya, Oguz 15 September 2017 (has links)
La factorisation des tenseurs est au coeur des méthodes d'analyse des données massives multidimensionnelles dans de nombreux domaines, dont les systèmes de recommandation, les graphes, les données médicales, le traitement du signal, la chimiométrie, et bien d'autres.Pour toutes ces applications, l'obtention rapide de la décomposition des tenseurs est cruciale pour pouvoir traiter manipuler efficacement les énormes volumes de données en jeu.L'objectif principal de cette thèse est la conception d'algorithmes pour la décomposition de tenseurs multidimensionnels creux, possédant de plusieurs centaines de millions à quelques milliards de coefficients non-nuls. De tels tenseurs sont omniprésents dans les applications citées plus haut.Nous poursuivons cet objectif via trois approches.En premier lieu, nous proposons des algorithmes parallèles à mémoire distribuée, comprenant des schémas de communication point-à-point optimisés, afin de réduire les coûts de communication. Ces algorithmes sont indépendants du partitionnement des éléments du tenseur et des matrices de faible rang. Cette propriété nous permet de proposer des stratégies de partitionnement visant à minimiser le coût de communication tout en préservant l'équilibrage de charge entre les ressources. Nous utilisons des techniques d'hypergraphes pour analyser les paramètres de calcul et de communication de ces algorithmes, ainsi que des outils de partitionnement d'hypergraphe pour déterminer des partitions à même d'offrir un meilleur passage à l'échelle. Deuxièmement, nous étudions la parallélisation sur plate-forme à mémoire partagée de ces algorithmes. Dans ce contexte, nous déterminons soigneusement les tâches de calcul et leur dépendances, et nous les exprimons en termes d'une structure de données idoine, et dont la manipulation permet de révéler le parallélisme intrinsèque du problème. Troisièmement, nous présentons un schéma de calcul en forme d'arbre binaire pour représenter les noyaux de calcul les plus coûteux des algorithmes, comme la multiplication du tenseur par un ensemble de vecteurs ou de matrices donnés. L'arbre binaire permet de factoriser certains résultats intermédiaires, et de les ré-utiliser au fil du calcul. Grâce à ce schéma, nous montrons comment réduire significativement le nombre et le coût des multiplications tenseur-vecteur et tenseur-matrice, rendant ainsi la décomposition du tenseur plus rapide à la fois pour la version séquentielle et la version parallèle des algorithmes.Enfin, le reste de la thèse décrit deux extensions sur des thèmes similaires. La première extension consiste à appliquer le schéma d'arbre binaire à la décomposition des tenseurs denses, avec une analyse précise de la complexité du problème et des méthodes pour trouver la structure arborescente qui minimise le coût total. La seconde extension consiste à adapter les techniques de partitionnement utilisées pour la décomposition des tenseurs creux à la factorisation des matrices non-négatives, problème largement étudié et pour lequel nous obtenons des algorithmes parallèles plus efficaces que les meilleurs actuellement connus.Tous les résultats théoriques de cette thèse sont accompagnés d'implémentations parallèles,aussi bien en mémoire partagée que distribuée. Tous les algorithmes proposés, avec leur réalisation sur plate-forme HPC, contribuent ainsi à faire de la décomposition de tenseurs un outil prometteur pour le traitement des masses de données actuelles et à venir. / Tensor factorization has been increasingly used to analyze high-dimensional low-rank data ofmassive scale in numerous application domains, including recommender systems, graphanalytics, health-care data analysis, signal processing, chemometrics, and many others.In these applications, efficient computation of tensor decompositions is crucial to be able tohandle such datasets of high volume. The main focus of this thesis is on efficient decompositionof high dimensional sparse tensors, with hundreds of millions to billions of nonzero entries,which arise in many emerging big data applications. We achieve this through three majorapproaches.In the first approach, we provide distributed memory parallel algorithms with efficientpoint-to-point communication scheme for reducing the communication cost. These algorithmsare agnostic to the partitioning of tensor elements and low rank decomposition matrices, whichallow us to investigate effective partitioning strategies for minimizing communication cost whileestablishing computational load balance. We use hypergraph-based techniques to analyze computational and communication requirements in these algorithms, and employ hypergraphpartitioning tools to find suitable partitions that provide much better scalability.Second, we investigate effective shared memory parallelizations of these algorithms. Here, we carefully determine unit computational tasks and their dependencies, and express them using aproper data structure that exposes the parallelism underneath.Third, we introduce a tree-based computational scheme that carries out expensive operations(involving the multiplication of the tensor with a set of vectors or matrices, found at the core ofthese algorithms) faster by factoring out and storing common partial results and effectivelyre-using them. With this computational scheme, we asymptotically reduce the number oftensor-vector and -matrix multiplications for high dimensional tensors, and thereby rendercomputing tensor decompositions significantly cheaper both for sequential and parallelalgorithms.Finally, we diversify this main course of research with two extensions on similar themes.The first extension involves applying the tree-based computational framework to computingdense tensor decompositions, with an in-depth analysis of computational complexity andmethods to find optimal tree structures minimizing the computational cost. The second workfocuses on adapting effective communication and partitioning schemes of our parallel sparsetensor decomposition algorithms to the widely used non-negative matrix factorization problem,through which we obtain significantly better parallel scalability over the state of the artimplementations.We point out that all theoretical results in the thesis are nicely corroborated by parallelexperiments on both shared-memory and distributed-memory platforms. With these fastalgorithms as well as their tuned implementations for modern HPC architectures, we rendertensor and matrix decomposition algorithms amenable to use for analyzing massive scaledatasets.
16

Modélisation de la croissance pro-pauvre / Pro-poor growth Modelling

Ka, Ndéné 05 December 2016 (has links)
Cette thèse contribue à l'approche économétrique de la croissance pro-pauvre. Elle présente des apports théoriques et empiriques. En premier lieu, elle présente les différentes définitions, indices et politiques de croissance pro-pauvre proposées dans la littérature théorique. Elle examine également les modèles théoriques et empiriques portant sur les interactions entre distribution du revenu et croissance. Elle montre que les mesures traditionnelles, en plus de leurs caractères partiels, peuvent conduire à des résultats contradictoires. Pour contourner ces limites, cette thèse privilégie l'approche alternative qui consiste à utiliser des modèles économétriques. Cette dernière approche, bien qu'elle présente l'avantage d'inclure l'ensemble des dimensions de la pauvreté, souffre de deux types de biais : le biais de sélection et le biais d'endogeneité. Ces derniers s'expliquent par les limitations inhérentes des données : erreurs de mesures, points aberrants. En outre, les résultats obtenus avec cette approche sont sensibles aux formes fonctionnelles choisies. Ainsi, il y'a de bonnes raisons d'utiliser la régression Gini. Malheureusement, les régressions de type Gini n'existaient qu'en coupe instantanée et en séries temporelles. Ainsi, dans un second temps, cette thèse propose d'étendre la réflexion sur la régression Gini en panel. Elle introduit les estimateurs intragroupes, intergroupes, le test d'existence de l'effet individuel et l'estimateur Aitken Gini. Enfin, cette thèse présente des applications empiriques qui illustrent de façon concrète la robustesse de nos estimateurs. Elle s'intéresse particulièrement aux conséquences de la méthode d'estimation et à la section de l'échantillon. Elle conclut que le processus de croissance favorise la réduction de la pauvreté à condition que les inégalités de revenu soient maîtrisées. Mais aussi, que l'impact de la croissance agricole sur la réduction de la pauvreté varie en fonction du niveau de développement du pays. / This thesis contributes to the econometric approach to pro-poor growth. It presents theoretical and empirical contributions. First, it presents the different definitions, indices and the policies of pro-poor growth proposed in the theoretical literature. It also examines the theoretical and empirical models on the interactions between income distribution and growth. It shows that the traditional measures, in addition to their partial characters, can lead to contradictory results. To avoid these limits this thesis emphasizes the alternative approach by using econometric models. The latter approach, although it has the advantage of including all the dimensions of poverty, suffering from two types of bias: selection bias and bias of endogeneity. These are due to the limitations of the data: measurement error, outliers. In addition, the results obtained with this approach are sensitive to selected functional forms. So, There are good reasons to use the Gini regression. Unfortunately, the Gini regressions existed only cross sectional and time series. Thus, in a second time, this thesis proposes to extend the Gini regression on the panel. It introduces within and between estimators, the individual effect test and the Gini Aitken estimator. Finally, this thesis presents empirical applications that illustrate the robustness of our estimators. She is particularly interested in the consequences of the estimation method and the sample section. It concludes that the growth process promotes poverty reduction when income inequalities are overcome. But also, the impact of agricultural growth on poverty reduction varies depending on the country's level of development.
17

Décompositions spatio-temporelles pour l'étude des textures dynamiques : contribution à l'indexation vidéo / Spatio-temporal decompositions for the study of Dynamic Textures : contribution to video indexing

Dubois, Sloven 19 November 2010 (has links)
Nous nous intéresserons dans cette thèse à l'étude et la caractérisation des Textures Dynamiques (TDs), avec comme application visée l'indexation dans de grandes bases de vidéos. Ce thème de recherche étant émergent, nous proposons une définition des TDs, une taxonomie de celles-ci, ainsi qu'un état de l'art. La classe de TD la plus représentative est décrite par un modèle formel qui considère les TDs comme la superposition d'ondes porteuses et de phénomènes locaux. La construction d'outils d'analyse spatio-temporelle adaptés aux TDs est notre principale contribution. D'une part, nous montrons que la transformée en curvelets 2D+T est pertinente pour la représentation de l'onde porteuse. D'autre part, dans un objectif de décomposition des séquences vidéos, nous proposons d'utiliser l'approche par Analyse en Composantes Morphologiques. Notre contribution consiste en l'apport et l'étude de nouvelles stratégies de seuillage. Ces méthodes sont testées sur plusieurs applications: segmentation spatio-temporelle, décomposition de TDs, estimation du mouvement global d'une TD, ... Nous avons de plus montré que l'Analyse en Composantes Morphologiques et les approches multi-échelles donnent des résultats significatifs pour la recherche par le contenu et l'indexation de Textures Dynamiques de la base de données DynTex. Cette thèse constitue ainsi un premier pas vers l'indexation automatique de textures dynamiques dans des séquences d'images, et ouvre la voie à de nombreux développements sur ce sujet nouveau. Enfin, le caractère générique des approches proposées permet d'envisager leurs applications dans un cadre plus large mettant en jeu par exemple des données 3D. / This report is focused on the study and the characterization of Dynamic Textures (DTs), with the aim of video indexing in large databases. This research topic being new and emerging, we propose a taxonomy, a definition of DTs and a state of the art. The most representative DT class is described by a model that considers DTs as the superposition of several wavefronts and local oscillating phenomena. The design of spatio-temporal analysis tools adapted to DT is our main contribution. We first show that the 2D+T curvelet transform is relevant for representing wavefronts. In order to analyse and better understand the DTs, we propose in a second step to adapt the Morphological Component Analysis approach using new thresholding strategies. These methods are tested on several applications: decomposition of DTs, spatio-temporal segmentation, global motion estimation of a DT, ... We have shown that Morphological Component Analysis and multi-scale approaches enable significant results for content-based retrieval applications and dynamic texture indexing on the DynTex database. This thesis constitutes a first step towards automatic indexing of DTs in image sequences and opens the way for many new developments in this topic. Moreover, the proposed approaches are generic and could be applied in a broader context, for instance the processing of 3D data.
18

Estimation sur des bases orthogonales des propriétés thermiques de matériaux hétérogènes à propriétés constantes par morceaux

Godin, Alexandre 25 January 2013 (has links) (PDF)
Ce travail se propose de caractériser thermiquement des composites à microstructures complexes. Il s'agit de développer des méthodes d'estimation permettant d'identifier les propriétés thermiques des différentes phases en présence, ainsi que celles associées à leurs interfaces, à partir de mesures issues de la thermographie infrarouge. Cette estimation paramétrique nécessite la connaissance au préalable de la structure géométrique de l'échantillon. Le premier objectif concerne donc l'identification de la structure de l'échantillon testé par la discrimination des différentes phases et interfaces. Une fois la structure de l'échantillon connue, le second objectif est l'identification des paramètres thermiques des différents constituants ainsi que ceux de leurs interfaces. On se propose d'exploiter deux tests spécifiques utilisant le même dispositif expérimental. Deux méthodes mathématiques différentes ont été développées et utilisées pour exploiter les mesures de champ issues du premier test et permettre de retrouver la microstructure de l'échantillon. La première est fondée sur la décomposition en valeurs singulières des données de températures recueillies. Il est montré que cette méthode permet d'obtenir des représentations de la microstructure de très bonne qualité à partir de mesures même fortement bruitées. La seconde méthode permet de raffiner les résultats obtenus à l'aide de la méthode précédente. Elle repose sur la résolution d'un problème d'optimisation sous contraintes en exploitant la technique dite Level-Set pour identifier les frontières des différents constituants de l'échantillon. L'étape d'identification des propriétés thermiques des constituants et des interfaces exploite les mesures de champs issues du second test expérimental. La méthode développée, la SVD-FT combine des techniques de décompositions en valeurs singulières avec desfonctions tests particulières pour dériver des estimateurs linéaires des propriétés recherchées.Cette méthode permet de limiter les effets du bruit de mesure sur la qualité de l'estimation et de s'affranchir des opérations de filtrage des données.
19

Tree-Representation of Set Families in Graph Decompositions and Efficient Algorithms

Bui-Xuan, Binh-Minh 09 September 2008 (has links) (PDF)
Ce manuscrit de thèse développe certains aspects autour de trois thèmes généraux, sur la représentation arborescente des familles d'ensembles, les décompositions de graphes, et les algorithmes de graphes. Les thèmes abordés vont de la combinatoire théorique à l'algorithmique en bio-informatique, en passant par plusieurs décompositions de graphes et aussi par l'optimisation combinatoire.<br /><br />La première moitié du manuscrit développe deux études. D'abord, afin d'estimer le nombre de familles d'ensembles satisfaisant certains axiomes de clôture, de nouveaux outils et techniques pour obtenir des représentations arborescentes de celles-ci ont été développés. Puis, l'étude se poursuit avec une des applications des propriétés ci-dessus : celle concernant les décompositions de graphes.<br /><br />La deuxième moitié du manuscrit est consacrée aux applications des décompositions de graphes dans l'algorithmique de graphes. Trois problèmes algorithmiques seront à l'étude.<br />Dans chacun des trois, il est montré pourquoi et comment on peut appliquer l'idée de la décomposition de graphes pour résoudre le problème posé de manière efficace.<br />Il est également montré comment appliquer les trois solutions proposées pour résoudre trois autres problèmes d'algorithmique de graphes.
20

Neighbour-distinguishing decompositions of graphs / Décompositions de graphes voisins-distinguantes

Senhaji, Mohammed 14 September 2018 (has links)
Dans cette thèse nous explorons différentes décompositions de graphes. Le titre de la présente thèse est dû au fait que la majorité de ces décompositions sont des décompositions voisin-distinguantes. En d'autres mots, nous pouvons en extraire des colorations propres des sommets. La question principale présentée dans cette thèse a été introduite par Karoński, Łuczak et Thomason: Est il possible de pondérer les arêtes d'un graphes avec les poids 1, 2 et 3, afin que tous les sommets voisins soient distingués par la somme des poids de leurs arêtes incidentes ? Cette question deviendra plus tard la fameuse 1-2-3 Conjecture. Nous présentons différentes variantes de la 1-2-3 Conjecture, ainsi que leurs liens avec les décompositions localement irrégulières. Nous nous intéressons tant à des problèmes d'optimisation qu'à des problèmes algorithmiques. Nous commençons par introduire une variante équitable des arête-pondérations voisin-somme-distinguantes, où chaque poids doit être utilisé le même nombre de fois (à l'unité près). Ensuite nous présentons une variante injective ou chaque poids est utilisé au plus une seule fois. Ce qui est un cas particulier de la variante équitable. De plus les pondérations injectives sont une variante locale des étiquetages anti-magiques. Ensuite nous modifions les conditions de distinction entre voisin en introduisant une variante 2-distinguante. les pondérations voisins-somme-2-distinguantes requierent que deux sommets voisins dans le graphe aient des sommes incidentes qui diffèrent d'au moins 2. Nous étudions le poids maximum minimal dans de telles pondérations pour certaines familles de graphes, ainsi que des problèmes de complexité. Dû aux liens entre les pondérations voisins-sommet-distinguantes et les décompositions localement irrégulières, nous nous sommes aussi intéressé à ces dernières, particulièrement pour les graphes sub-cubiques, ainsi qu'à d'autres variantes des décompositions localement irrégulières. Finalement nous présentons un jeu de pondérations à deux joueurs, ainsi qu'une théorie de décompositions qui unifie les pondérations voisin-somme-distinguantes et les décompositions localement irrégulières. / In this thesis we explore graph decompositions under different constraints. The title of the is due to the fact that most of these decompositions are neighbour-distinguishing. That is, we can extract from each such decomposition a proper vertex colouring. Moreover, most of the considered decompositions are edge partitions, and therefore can be seen as edge-colourings. The main question presented in this thesis is was introduced by Karoński, Łuczak and Thomason in [KLT04]: Can we weight the edges of a graph G, with weights 1, 2, and 3, such that any two of adjacent vertices of G are distinguished by the sum of their incident weights ? This question later becomes the famous 1-2-3 Conjecture. In this thesis we explore several variants of the 1-2-3 Conjecture, and their links with locally irregular decompositions. We are interested in both optimisation results and algorithmic problems. We first introduce an equitable version of the neighbour-sum- distinguishing edge-weightings, that is a variant where we require every edge weight to be used the same number of times up to a difference of 1. Then we explore an inject- ive variant where each edge is assigned a different weight, which yields necessarily an equitable weighting. This gives us first general upper bounds on the equitable version. Moreover, the injective variant is also a local version of the well-known antimagic la- belling. After that we explore how neighbour-sum-distinguishing weightings behave if we require sums of neighbouring vertices to differ by at least 2. Namely, we present results on the smallest maximal weight needed to construct such weightings for some classes of graphs, and study some algorithmic aspects of this problem. Due to the links between neighbour-sum-distinguishing edge weightings and locally irregular decompositions, we also explore the locally irregular index of subcubic graphs, along with other variants of the locally irregular decomposition problem. Finally, we present a more general work to- ward a general theory unifying nsd edge-weightings and locally irregular decompositions. We also present a 2-player game version of neighbour-sum-distinguishing edge-weightings and exhibit sufficient conditions for each player to win the game.

Page generated in 0.1097 seconds