Nos recherches traitent de coloration de graphes avec des contraintes de distance (coloration de packing) ou des contraintes sur le voisinage (coloration de Grundy). Soit S={si| i in N*} une série croissante d’entiers. Une S -coloration de packing est une coloration propre de sommets telle que tout ensemble coloré i est un si-packing (un ensemble où tous les sommets sont à distance mutuelle supérieure à si). Un graphe G est (s1,... ,sk)-colorable si il existe une S -coloration de packing de G avec les couleurs 1, ...,,k. Une coloration de Grundy est une coloration propre de sommets telle que pour tout sommet u coloré i, u est adjacent à un sommet coloré j, pour chaque j<i.Dans cette exposé, nous présentons des résultats connus à propos de la S-coloration de packing. Nous apportons de nouveaux résultats à propos de la S-coloration de packing, pour des classes de graphes telles que les chemins, les cycles et les arbres. Nous étudions en détail la complexité du problème de complexité associé à la S-coloration de packing, noté S -COL. Pour certaines instances de S -COL, nous caractérisons des dichotomies entre problèmes NP-complets et problèmes résolubles en tempspolynomial. Nous nous intéressons aux différentes grilles infinies, les grilles hexagonale, carrée, triangulaire et du roi et nous déterminons des propriétés de subdivisions d’un i-packing en plusieurs j-packings, avec j>i. Ces résultats nous permettent de déterminer des S-colorations de packings de ces grilles pour plusieurs séries d’entiers. Nous examinons une classe de graphe jamais étudiée en ce qui concerne la S -coloration de packing: les graphes subcubiques. Nous déterminons que tous les graphes subcubiques sont (1,2,2,2,2,2,2)-colorables et (1,1,2,2,3)-colorables. Un certain nombre de résultats sont prouvés pour certaines sous-classes des graphes subcubiques. Pour finir, nous nous intéressons au nombre de Grundy des graphes réguliers. Nous déterminons une caractérisation des graphes cubiques avec un nombre de Grundy de 4. De plus, nous prouvons que tous les graphes r-réguliers sans carré induit ont pour nombre de Grundy de r+1, pour r<5. / Our research are about graph coloring with distance constraints (packing coloring) or neighborhood constraints (Grundy coloring). Let S={si| i in N*} be a non decreasing sequence of integers. An S-packing coloring is a proper coloring such that every set of color i is an si-packing (a set of vertices at pairwise distance greater than si). A graph G is (s1,... ,sk)-colorable if there exists a packing coloring of G with colors 1,... ,k. A Grundy coloring is a proper vertex coloring such that for every vertex of color i, u is adjacent to a vertex of color j, for each j<i.In this presentation, we present results about S-packing coloring. We prove new results about the S-coloring of graphs including paths, cycles and trees. We study the complexity problem associated to the S-packing coloring, this problem is denoted S-COL. For some instances of S-COL, we characterize dichotomy between NP-complete problems and problems solved by a polynomial time algorithm. We study also different lattices, the hexagonal, square, triangular and king lattices. We determine properties on the subdivision of an i-packing in several j-packings, for j>i. These results allow us to determine S-packing coloring of these lattices for several sequences of integers. We examine a class of graph that has never been studied for S-packing coloring: the subcubic graphs. We determine that every subcubic graph is (1,2,2,2,2,2,2)-colorable and (1,1,2,2,3)-colorable. Few results are proven about some subclasses. Finally, we study the Grundy number of regular graphs. We determine a characterization of the cubic graphs with Grundy number 4. Moreover, we prove that every r-regular graph without induced square has Grundy number r+1, for r<5.

Les problèmes d’ordonnancement de rendez-vous en tête-à-tête sont des problèmes dans lesquels des personnes souhaitent se rencontrer par deux lors de courts rendez-vous qui se déroulent lors d’une session unique. Dans cette thèse, nous référençons plusieurs applications de ce type de problèmes et proposons des notations qui généralisent les notations standards de problèmes d’ordonnancement α|β|γ. Nous nous intéressons en particulier à un cas dans lequel deux populations distinctes se rencontrent, des participants peuvent arriver en retard et des rencontres sont interdites. L’objectif est de minimiser le nombre maximal d’attentes des participants. Nous étudions dans un premier temps la complexité de ces problèmes : nous démontrons que plusieurs cas sans rencontre interdite sont polynomiaux et que le cas général est NP-complet au sens fort. Nous proposons ensuite des bornes inférieures. Puis nous développons plusieurs méthodes de résolution. Des modèles de programmation linéaire en nombres entiers et un modèle de programmation par contraintes sont tout d’abord proposés. Des règles de dominance permettant de limiter les symétries sont intégrées à ces modèles dans le but de limiter l’espace des solutions. Enfin, nous proposons une recherche à divergence limitée (limited discrepancy search) qui est une méthode approchée basée sur l’exploration d’un arbre de recherche tronqué. Dans cette méthode, nous exploitons le plus possible les propriétés de symétrie du problème pour faciliter la convergence vers une bonne solution. Toutes ces méthodes sont testées et comparées sur un ensemble de 300 instances générées aléatoirement d’après des paramètres réalistes. / One-to-one meeting scheduling problems are problems where a population of actors want to meet each other during short time slots that take place in a single session. In this thesis, we reference several applications of this type of problems found in the literature and introduce a notation extending the well-known scheduling notation α|β|γ. We are particularly interested in a case in which two distinct populations meet, participants may arrive late and some meetings are forbidden. The objective is to minimize the maximum number of participants waiting slots. First, we study the complexity of these problems: we show that several cases with no forbidden meeting are polynomial and that the general case is NP-complete in the strong sense. We then propose lower bounds. After that, we develop several resolution methods. Integer linear programming models and a constraint programming model are developed. To limit the solution space, we add dominance rules based on symmetries to these methods. Finally, we present a limited discrepancy search (i.e. an approximate method based on the exploration of a truncated tree search). In this method, we use as much as possible the symmetry properties of the problem to facilitate the convergence to a good solution. All these methods are tested and compared on a set of 300 randomly generated instances from realistic parameters.

L'objet de cette thèse est l'étude des aspects algorithmiques du vote par approbation. Il s'agit principalement d'une étude théorique des enjeux computationnels soulevés par le vote par approbation dans des contextes de décisions variés. Cependant, j'étudie aussi des questions plus proches de la théorie classique du choix social et je conduis de brèves études expérimentales.Dans un premier temps, l'étude se porte sur une famille générale de règles de vote pour les élections de comités et les référendums multiples à l'aide du vote par approbation. Dans un second temps, je porte mon attention sur un contexte plus général, le vote par approbation sur domaines combinatoires en se basant sur des préférences conditionnelles. Finalement, je me place dans le cadre du vote avec préférences incomplètes pour étudier les problèmes de vainqueurs possibles et nécessaires dans le vote par approbation. / The subject of this thesis is the study of computational aspects of approval voting. Most of the works are theoretical results about computational issues raised by approval voting, in many different settings. However, I also study some questions that are more related to classical choice theory, and some problems are investigated through experimental analysis.Firstly, I study a general family of rules for approval voting in the context of committee elections and multiple referenda. Secondly, I focus on a more general setting, approval voting in combinatorial domains, based on conditional preferences. Finally, I consider approval voting in the context of incomplete preferences, to study the possible and necessary winner problems.

Cette thèse s'intéresse à la conception et le développement des techniques de bioinfor- matique qui peuvent faciliter l'utilisation de l'approche metabarcoding pour mesurer la diversité d'espèces. Le metabarcoding peut être utilisé avec le séquencage haut débit pour l'identification d'espèces multiples à partir d'un seul échantillon environnemental. La véritable force du metabarcoding réside dans l'utilisation de barcode marqueurs choisi pour une étude particulière et l'identification d'espèces ou des taxons peut être réalisé avec des marqueurs soigneusement conçu. Avec l'avancement des techniques haut débit de séquençage, une énorme quantité des données de séquences est produit qui contient un nombres substantiel des mutations. Ces mutations posent un grand problème pour les estimations correctes de la biodiversité et pour le d'assignation de taxon. Les trois problèmes majeurs dans le domaine de la bioinformatique que j'ai abordés dans cette thèse sont: i) évaluer la qualité d'une barcode marker , ii) concevoir des nouveaux région barcode et iii) d'analyser les données de séquençage pour traiter les erreurs et éliminer le bruit en séquences. Pour évaluer la qualité d'un barcode marker, on a développé deux mesures quantita- tive,formelle: la couverture (Bc) et la spécificité (Bs). La couverture donne une mesure de universalité d'une pairs de primer pour amplifier un large nombre de taxa, alors que la spécificité donne une mesure de capacité à discriminer entre les différents taxons. Ces mesures sont très utiles pour le classement des barcode marker et pour sélectionner les meilleurs markers. Pour trouver des nouveaux région barcode notamment pour les applications metabarcod- ing, j'ai développé un logiciel, ecoPrimers3. Basé sur ces deux mesures de qualité et de l'information taxinomique intégré, ecoPrimers nous permet de concevoir barcode markers pour n'importe quel niveau taxonomique . En plus, avec un grand nombre de paramètres réglables il nous permet de contrôler les propriétés des amorces. Enfin, grâce a des algorithmes efficaces et programmé en langage C, ecoPrimers est suffisamment efficace pour traiter des grosses bases de données, y compris génomes bactériens entièrement séquencés. Enfin pour traiter des erreurs présentes dans les données de séquencage , nous avons analysé un ensemble simple d'échantillons de PCR obtenus à partir de l'analyse du régime alimentaire de Snow Leopard. En mesurant les corrélations entre les différents paramètres des erreurs, nous avons observé que la plupart des erreurs sont produites pendant l'amplification par PCR. Pour détecter ces erreurs, nous avons développé un algorithme utilisant les graphes, qui peuvent différencier les vrai séquences des erreurs induites par PCR. Les résultats obtenus à partir de cet algorithme a montré que les données de-bruitée a donnent une estimation réaliste de la diversité des espèces étudiées dans les Alpes françaises. / This thesis is concerned with the design and development of bioinformatics techniques that can facilitate the use of metabarcoding approach for measuring species diversity. Metabarcoding coupled with next generation sequencing techniques have a strong po- tential for multiple species identification from a single environmental sample. The real strength of metabarcoding resides in the use of barcode markers chosen for a particular study. The identification at species or higher level taxa can be achieved with carefully designed barcode markers. Moreover with the advent of high throughput sequencing techniques huge amount of sequence data is being produced that contains a substantial level of mutations. These mutations pose a problem for the correct estimates of biodi- versity and for the taxon assignation process. Thus the three major challenges that we addressed in this thesis are: evaluating the quality of a barcode region, designing new barcodes and dealing with errors occurring during different steps of an experiment. To assess the quality of a barcode region we have developed two formal quantitative mea- sures called barcode coverage (Bc) and barcode specificity (Bs). Barcode coverage is concerned with the property of a barcode to amplify a broad range of taxa, whereas barcode specificity deals with its ability to discriminate between different taxa. These measures are extremely useful especially for ranking different barcodes and selecting the best markers. To deal with the challenge of designing new barcodes for metabarcoding applications we have developed an efficient software called ecoPrimers. Based on the above two quality measures and with integrated taxonomic information, ecoPrimers1 enables us to design primers and their corresponding barcode markers for any taxonomic level. Moreover with a large number of tunable parameters it allows us to control the properties of primers. Finally, based on efficient algorithms and implemented in C language, ecoPrimers is efficient enough to deal with large data bases including fully sequenced bacterial genomes. Finally to deal with errors present in DNA sequence data, we have analyzed a simple set of PCR samples obtained from the diet analysis of snow leopard. We grouped closely related sequences and by measuring the correlation between different parameters of mutations, we have shown that most of the errors were introduced during PCR amplification. In order to deal with such errors, we have further developed an algorithm using graphs approach, that can differentiate true sequences from PCR induced errors. The results obtained from this algorithm showed that de-noised data gave a realistic estimate of species diversity studied in French Alpes. This algorithm is implemented in program obiclean.