Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphes.

Le but principal de ce manuscrit est de montrer que certaines familles de graphes sont des graphes plongeables dans l'hypercube. Un problème d'une autre nature sera traité, il concerne la partition de l'hypercube en des cycles sommet-disjoints de longueur paires. Nous prouvons que l'hypercube de dimension n peut être partitionné en k cycles sommet-disjoints si k

Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphes. / In this thesis, we define a new class of graphs : the hypochordal graphs. These graphs satisfy that for any path of length two, there exists a chord or another path of length two between its two endpoints. This class can represent robust networks. Indeed, we show that in such graphs, in the case of an edge or a vertex deletion, the distance beween any pair of nonadjacent vertices remains unchanged. Then, we study several properties for this class of graphs. Especially, after introducing a family of specific partitions, we show the relations between some of these partitions and hypochordality. Moreover, thanks to these partitions, we characterise minimum hypochordal graph, that are, among connected hypochordal graphs, those that minimise the number of edges for a given number of vertices. In a second part, we study the complexity, for hypochordal graphs, of problems that are NP-hard in the general case. We first show that the classical problems of hamiltonian cycle, colouring, maximum clique and maximum stable set remain NP-hard for this class of graphs. Then, we analyse graph modification problems : deciding the minimal number of edges to add or delete from a graph, in order to obtain an hypochordal graph. We study the complexity of these problems for sevaral classes of graphs.

La sécurisation inhérente aux échanges dans les environnements dynamiques et distribués, dépourvus d’une coordination centrale et dont la topologie change perpétuellement, est un défi majeur. Dans le cadre de cette thèse, on se propose en effet de définir une infrastructure de sécurité adaptée aux contraintes des systèmes P2P actuels. Le premier volet de nos travaux consiste à proposer un intergiciel, appelé SEMOS, qui gère des sessions sécurisées et mobiles. SEMOS permet en effet de maintenir les sessions sécurisées actives et ce, même lorsque la configuration réseau change ou un dysfonctionnement se produit. Cette faculté d’itinérance est rendue possible par la définition d’un nouveau mécanisme de découplage afin de cloisonner l’espace d’adressage de l’espace de nommage ; le nouvel espace de nommage repose alors sur les tables de hachage distribuées (DHT). Le deuxième volet définit un mécanisme distribué et générique d’échange de clés adapté à l’architecture P2P. Basé sur les chemins disjoints et l’échange de bout en bout, le procédé de gestion des clés proposé est constitué d’une combinaison du protocole Diffie-Hellman et du schéma à seuil(k, n) de Shamir. D’une part, l’utilisation des chemins disjoints dans le routage des sous-clés compense l’absence de l’authentification certifiée, par une tierce partie, consubstantielle au protocole Diffie-Hellman et réduit, dans la foulée, sa vulnérabilité aux attaques par interception. D’autre part, l’extension de l’algorithme Diffie-Hellman par ajout du schéma à seuil (k, n) renforce substantiellement sa robustesse notamment dans la segmentation des clés et/ou en cas de défaillances accidentelles ou délibérées dans le routage des sous-clés. Enfin, les sessions sécurisées mobiles sont évaluées dans un réseau virtuel et mobile et la gestion des clés est simulée dans un environnement générant des topologies P2P aléatoires. / Securing communications in distributed dynamic environments, that lack a central coordination point and whose topology changes constantly, is a major challenge.We tackle this challenge of today’s P2P systems. In this thesis, we propose to define a security infrastructure that is suitable to the constraints and issues of P2P systems. The first part of this document presents the design of SEMOS, our middleware solution for managing and securing mobile sessions. SEMOS ensures that communication sessions are secure and remain active despite the possible disconnections that can occur when network configurations change or a malfunction arises. This roaming capability is implemented via the definition of a new addressing space in order to split up addresses for network entities with their names ; the new naming space is then based on distributed hash tables(DHT). The second part of the document presents a generic and distributed mechanism for a key exchange method befitting to P2P architectures. Building on disjoint paths andend-to-end exchange, the proposed key management protocol consists of a combination of the Diffie-Hellman algorithm and the Shamir’s (k, n) threshold scheme. On the onehand, the use of disjoint paths to route subkeys offsets the absence of the third party’s certified consubstantial to Diffie-Hellman and reduces, at the same time, its vulnerability to interception attacks. On the other hand, the extension of the Diffie-Hellman algorithm by adding the threshold (k, n) scheme substantially increases its robustness, in particular in key splitting and / or in the case of accidental or intentional subkeys routing failures. Finally, we rely on a virtual mobile network to assess the setup of secure mobile sessions.The key management mechanism is then evaluated in an environment with randomly generated P2P topologies.

Cette thèse étudie des systèmes locaux de gestion de transfert de pétrole ayant une architecture de réseau de canalisation. Pour leur représentativité, deux systèmes localisés au Venezuela et appartenant à l'entreprise PDVSA (Pétroles du Venezuela) ont été retenus pour illustrer les méthodes proposées et les valider : le Terminal Maritime de Pétrole de Guaraguao et le Centre de Stockage de Punta de Palmas. Dans ces réseaux des connexions, appelées " alignements ", sont établies en ouvrant/fermant des vannes à travers d'un système SCADA (Supervisory Control and Data Acquisition). Le choix d'un alignement doit tenir compte de critères d'optimisation. La minimisation des interférences avec d'autres alignements, liée à la notion de capacité opérative, a été identifiée comme le critère de choix le plus important. Les contributions de cette thèse reposent sur une modélisation sous forme de graphes, et sur des algorithmes appartenant au domaine de la recherche opérationnelle. Elles contribuent à fournir aux opérateurs de supervision des outils d'analyse permettant d'optimiser le choix des alignements. Des indicateurs permettant de quantifier l'impact des opérations d'alignement ou des défaillances, sur la capacité opérative du système, sont proposés. La minimisation de l'impact sur la capacité opérative, va correspondre à la minimisation des interférences avec des alignements potentiels. Un algorithme de calcul de ces indicateurs, est présenté, ainsi que des algorithmes de recherche de chemin, de détermination d'éléments critiques, et de recherche d'alignements utilisant des pompes. Ces algorithmes sont basés sur des algorithmes classiques s'adressant au problème du plus court chemin, du flot maximum et du nombre maximum de chemins disjoints. Cependant, ils utilisent des méthodes innovantes, comme l'ajout de contraintes considérant l'existence de sous-types d'alignements, le calcul dynamique des coûts des chemins à partir de son impact sur la capacité opérative, et la recherche de chemins via un point intermédiaire obligatoire. Les contributions sont potentiellement applicables dans des domaines autres que le transport de pétrole. Les algorithmes ont été mis en œuvre en utilisant le langage Python et ont été testés en utilisant les données réelles des réseaux étudiés. L'objectif à moyen terme de ces travaux est le développement d'un logiciel d'assistance à la prise de décision.

Cette thèse s'inscrit dans le contexte de la vidéosurveillance "intelligente", et s'intéresse à la supervision de réseaux de caméras à champs disjoints, contrainte classique lorsque l'on souhaite limiter l'instrumentation du bâtiment. Il s'agit là de l'un des cas d'application du problème de la ré-identification de personnes. À ce titre, la thèse propose une approche se démarquant de l'état de l'art qui traite classiquement le problème sous l'aspect description, via la mise en correspondance de signatures image à image. Nous l'abordons ici sous l'aspect filtrage : comment intégrer la ré-identification de personne dans un processus de suivi multi-pistes, de manière à maintenir des identités de pistes cohérentes, malgré des discontinuités dans l'observation. Nous considérons ainsi une approche suivi et mises en correspondance, au niveau caméra et utilisons ce module pour ensuite raisonner au niveau du réseau. Nous décrivons dans un premier temps les approches classiques de ré-identification, abordées sous l'aspect description. Nous proposons ensuite un formalisme de filtrage particulaire à états continus et discret pour estimer conjointement position et identité de la cible au cours du temps, dans chacune des caméras. Un second étage de traitement permet d'intégrer la topologie du réseau et les temps d'apparition pour optimiser la ré-identification au sein du réseau. Nous démontrons la faisabilité de l'approche en grande partie sur des données issues de réseaux de caméras déployés au sein du laboratoire, étant donné le manque de données publiques concernant ce domaine. Nous prévoyons de mettre en accès public ces banques de données.

L'étude des cycles, flots et chemins des graphes est intimement liée au développement de l'optimisation combinatoire. Dans l'introduction nous mettons en parallèle ces concepts à partir de résultats classiques, et les deux autres parties de la thèse développent les nouveaux résultats dans deux directions différentes. La première porte sur les problèmes d'existence de multiflots entiers. Plusieurs paramètres naturels s'appliquent à ces problèmes, générant plus d'une centaine de cas. Après un rappel des résultats de la littérature sous une forme synthétique, nous résolvons plusieurs problèmes ouverts. En particulier, nous montrons que trouver deux flots disjoints dans les graphes planaires est un problème NP-complet. Nous donnons aussi un algorithme polynomial pour router les digraphes planaires acycliques eulériens, lorsque le nombre de classes d'arcs de demande est fixé. Ensuite, nous nous intéressons au problème consistant à trouver une plus courte marche fermée passant par tous les sommets d'un graphe. Spéciquement, nous cherchons à caractériser les graphes pour lesquels une bonne caractérisation est donnée par des empilements d'ensembles éclatants. Nous présentons quelques résultats de nature polyédrale, puis étudions le cas des cographes et des graphes d'intervalles.

Cette thèse étudie des systèmes locaux de gestion de transfert de pétrole ayant une architecture de réseau de canalisation. Pour leur représentativité, deux systèmes localisés au Venezuela et appartenant à l'entreprise PDVSA (Pétroles du Venezuela) ont été retenus pour illustrer les méthodes proposées et les valider : le Terminal Maritime de Pétrole de Guaraguao et le Centre de Stockage de Punta de Palmas. Dans ces réseaux des connexions, appelées « alignements », sont établies en ouvrant/fermant des vannes à travers d'un système SCADA (Supervisory Control and Data Acquisition). Le choix d'un alignement doit tenir compte de critères d'optimisation. La minimisation des interférences avec d'autres alignements, liée à la notion de capacité opérative, a été identifiée comme le critère de choix le plus important. Les contributions de cette thèse reposent sur une modélisation sous forme de graphes, et sur des algorithmes appartenant au domaine de la recherche opérationnelle. Elles contribuent à fournir aux opérateurs de supervision des outils d'analyse permettant d'optimiser le choix des alignements. Des indicateurs permettant de quantifier l'impact des opérations d'alignement ou des défaillances, sur la capacité opérative du système, sont proposés. La minimisation de l'impact sur la capacité opérative, va correspondre à la minimisation des interférences avec des alignements potentiels. Un algorithme de calcul de ces indicateurs, est présenté, ainsi que des algorithmes de recherche de chemin, de détermination d'éléments critiques, et de recherche d'alignements utilisant des pompes. Ces algorithmes sont basés sur des algorithmes classiques s'adressant au problème du plus court chemin, du flot maximum et du nombre maximum de chemins disjoints. Cependant, ils utilisent des méthodes innovantes, comme l'ajout de contraintes considérant l'existence de sous-types d'alignements, le calcul dynamique des coûts des chemins à partir de son impact sur la capacité opérative, et la recherche de chemins via un point intermédiaire obligatoire. Les contributions sont potentiellement applicables dans des domaines autres que le transport de pétrole. Les algorithmes ont été mis en œuvre en utilisant le langage Python et ont été testés en utilisant les données réelles des réseaux étudiés. L'objectif à moyen terme de ces travaux est le développement d'un logiciel d'assistance à la prise de décision. / This thesis studies local crude oil transportation systems with a pipe network architecture. Two representative systems, belonging to PDVSA (Venezuelan oil company), have been studied: the Guaraguao Crude Oil Seaport and the Punta de Palmas Tanks Yard. In this systems, connections, called "alignments", are established by opening/closing valves using a SCADA(Supervisory Control and Data Acquisition) system. Alignment choice is made based on optimization criteria. Interferences minimization with other alignments, related to the notion of operative capacity, has been identified as the most important criterion. The contributions of this thesis are based on graph modelling and algorithms from operational research. The main goal is to provide analysis tools allowing alignment choice optimization. Indexes permitting the quantification of alignments or failures impact on the operative capacity of the system are proposed. Minimizing the impact on the operative capacity will correspond to minimizing interferences with potential alignments. An algorithm computing these indexes is presented, as well as complementary developments such as a path search algorithm, an algorithm for critical elements determination, and algorithm for alignments using pumps. These algorithms are based on classical algorithms for the shortest path problem, the maximum flow problem and the maximum disjoint paths problem. However, they use innovative methods such as adding constraints when considering alignment sub-types, the dynamic computation of path costs based on their impact on operative capacity, and path search considering an obligatory intermediate node. These contributions can potentially be applied in areas other than oil transportation. The algorithms had been implemented in Python and had been tested using real data from the studied systems. The middle term goal of these works is the development of assistance software for decision making.

Cette thèse étudie la coloration d'arcs et de cycles dans les graphes orientés. Elle se concentre sur les sujets suivants : la coloration propre d'arcs avec des sommet-distingué dans les graphes orientés, les cycles courts dans les graphes orientés avec des sous-graphes interdits, les cycles sommet-disjoints dans dans les tournois bipartis, les cycle-facteurs dans les tournois bipartis régulier et les arcs universels dans les tournois. La thèse est basée sur cinq articles originaux publiés ou présentés dans des journaux. Les principaux résultats sont les suivants. Nous introduisons la coloration propre d'arcs avec des sommet-distingué dans les graphes orientés. Nous avons proposé une conjecture sur le nombre arc-chromatique sommet-distingué et nous avons aussi donné quelque résultats partiels. Nous avons étendu un résultat de Razborov en prouvant que la conjecture de Caccetta-Häggkvist est vraie pour certains graphes orientés avec des sous-graphes interdits. Nous avons montré que chaque tournoi biparti avec degré sortant minimum au moins qr-1 contient r cycles de sommets-disjoints de toutes longueurs possibles. Le cas spécial q=2 confirme le cas du tournoi biparti de la conjecture de Bermond-Thomassen. Nous avons montré que chaque tournoi biparti k-régulier avec k>2 que l'on notera B a deux cycles complémentaires de longueurs 6 et |V(B)-6|, à moins que B soit isomorphe à un graphe spécifique, étayant ainsi une conjecture sur des 2-cycles-facteurs dans les tournois bipartis. En outre, nous montrons que tous les tournois bipartis réguliers ont un k-cycle-facteur. Nous donnons une condition nécessaire et suffisante pour l'existence d'un arc universel dans un tournoi et nous caractérisons tous les tournois où chaque arc est universel. / In this thesis, we study arc colorings and cycles in digraphs. The following topics are considered: vertex-distinguishing proper arc colorings in digraphs, short cycles in digraphs with forbidden subgraphs , disjoint cycles in bipartite tournaments, cycle factors in regualr bipartite tournaments and universal arcs in tournaments. The main results are contained in five original articles published or submitted to an international journal. We introduce vertex-distinguishing proper arc colorings of digraphs. A conjecture on the vertex-distinguishing arc-chromatic number is given and some partial results are obtained. We extend a result of Razborov by proving that the Caccetta-Häggkvist conjecture is true for digraphs with certain induced forbidden subgraphs or with certain forbidden subgraphs. We show that every bipartite tournament with minimum outdegree at least qr-1 has r vertex disjoint cycles of any given possible lengths. The special case q=2 of the result verifies the bipartite tournament case of the Bermond-Thomassen conjecture. As a partial support of a conjecture on 2-cycle-factors in bipartite tournaments, we prove that every k-regular bipartite tournament B with k>2 has two complementary cycles of lengths 6 and |V(B)|-6, unless B is isomorphic to a special digraph. Besides, we show that every k-connected regular bipartite tournament has a k-cycle-factor. We also give a sufficient and necessary condition for the existence of a universal arc in a tournament and characterize all the tournaments in which every arc is universal.

La théorie de l'information quantique s'est développée à une vitesse fulgurante au cours des vingt dernières années, avec des analogues et extensions des théorèmes de codage de source et de codage sur canal bruité pour la communication unidirectionnelle. Pour la communication interactive, un analogue quantique de la complexité de la communication a été développé, pour lequel les protocoles quantiques peuvent performer exponentiellement mieux que les meilleurs protocoles classiques pour certaines tâches classiques. Cependant, l'information quantique est beaucoup plus sensible au bruit que l'information classique. Il est donc impératif d'utiliser les ressources quantiques à leur plein potentiel. Dans cette thèse, nous étudions les protocoles quantiques interactifs du point de vue de la théorie de l'information et étudions les analogues du codage de source et du codage sur canal bruité. Le cadre considéré est celui de la complexité de la communication: Alice et Bob veulent faire un calcul quantique biparti tout en minimisant la quantité de communication échangée, sans égard au coût des calculs locaux. Nos résultats sont séparés en trois chapitres distincts, qui sont organisés de sorte à ce que chacun puisse être lu indépendamment. Étant donné le rôle central qu'elle occupe dans le contexte de la compression interactive, un chapitre est dédié à l'étude de la tâche de la redistribution d'état quantique. Nous prouvons des bornes inférieures sur les coûts de communication nécessaires dans un contexte interactif. Nous prouvons également des bornes atteignables avec un seul message, dans un contexte d'usage unique. Dans un chapitre subséquent, nous définissons une nouvelle notion de complexité de l'information quantique. Celle-ci caractérise la quantité d'information, plutôt que de communication, qu'Alice et Bob doivent échanger pour calculer une tâche bipartie. Nous prouvons beaucoup de propriétés structurelles pour cette quantité, et nous lui donnons une interprétation opérationnelle en tant que complexité de la communication quantique amortie. Dans le cas particulier d'entrées classiques, nous donnons une autre caractérisation permettant de quantifier le coût encouru par un protocole quantique qui oublie de l'information classique. Deux applications sont présentées: le premier résultat général de somme directe pour la complexité de la communication quantique à plus d'une ronde, ainsi qu'une borne optimale, à un terme polylogarithmique près, pour la complexité de la communication quantique avec un nombre de rondes limité pour la fonction « ensembles disjoints ». Dans un chapitre final, nous initions l'étude de la capacité interactive quantique pour les canaux bruités. Étant donné que les techniques pour distribuer de l'intrication sont bien étudiées, nous nous concentrons sur un modèle avec intrication préalable parfaite et communication classique bruitée. Nous démontrons que dans le cadre plus ardu des erreurs adversarielles, nous pouvons tolérer un taux d'erreur maximal de une demie moins epsilon, avec epsilon plus grand que zéro arbitrairement petit, et ce avec un taux de communication positif. Il s'ensuit que les canaux avec bruit aléatoire ayant une capacité positive pour la transmission unidirectionnelle ont une capacité positive pour la communication interactive quantique. Nous concluons avec une discussion de nos résultats et des directions futures pour ce programme de recherche sur une théorie de l'information quantique interactive. / Quantum information theory has developed tremendously over the past two decades, with analogues and extensions of the source coding and channel coding theorems for unidirectional communication. Meanwhile, for interactive communication, a quantum analogue of communication complexity has been developed, for which quantum protocols can provide exponential savings over the best possible classical protocols for some classical tasks. However, quantum information is much more sensitive to noise than classical information. It is therefore essential to make the best use possible of quantum resources. In this thesis, we take an information-theoretic point of view on interactive quantum protocols and study the interactive analogues of source compression and noisy channel coding. The setting we consider is that of quantum communication complexity: Alice and Bob want to perform some joint quantum computation while minimizing the required amount of communication. Local computation is deemed free. Our results are split into three distinct chapters, and these are organized in such a way that each can be read independently. Given its central role in the context of interactive compression, we devote a chapter to the task of quantum state redistribution. In particular, we prove lower bounds on its communication cost that are robust in the context of interactive communication. We also prove one-shot, one-message achievability bounds. In a subsequent chapter, we define a new, fully quantum notion of information cost for interactive protocols and a corresponding notion of information complexity for bipartite tasks. It characterizes how much quantum information, rather than quantum communication, Alice and Bob must exchange in order to implement a given bipartite task. We prove many structural properties for these quantities, and provide an operational interpretation for quantum information complexity as the amortized quantum communication complexity. In the special case of classical inputs, we provide an alternate characterization of information cost that provides an answer to the following question about quantum protocols: what is the cost of forgetting classical information? Two applications are presented: the first general multi-round direct-sum theorem for quantum protocols, and a tight lower bound, up to polylogarithmic terms, for the bounded-round quantum communication complexity of the disjointness function. In a final chapter, we initiate the study of the interactive quantum capacity of noisy channels. Since techniques to distribute entanglement are well-studied, we focus on a model with perfect pre-shared entanglement and noisy classical communication. We show that even in the harder setting of adversarial errors, we can tolerate a provably maximal error rate of one half minus epsilon, for an arbitrarily small epsilon greater than zero, at positive communication rates. It then follows that random noise channels with positive capacity for unidirectional transmission also have positive interactive quantum capacity. We conclude with a discussion of our results and further research directions in interactive quantum information theory.