Cette thèse s'inscrit dans le cadre de la théorie des graphes, et porte plus particulièrement sur des problèmes de coloration de graphes. Dans cette thèse, nous nous intéressons à l'utilisation et au développement de la méthode de déchargement, un argument de comptage qui exploite fortement la structure du graphe. Cette méthode est décisive dans la preuve du Théorème des Quatre Couleurs. Nous donnons d'abord une vue d'ensemble des outils de déchargement que nous utilisons dans ce travail, entre les méthodes élégantes mises en application, et les astuces développées. Dans le cadre de la coloration d'arêtes par liste, nous résolvons la Conjecture de Coloration par Liste faible dans le cas des graphes planaires de degré maximum 8, en prouvant qu'on peut colorier par liste les arêtes de ces derniers avec 9 couleurs seulement. Ceci améliore un résultat de Borodin de 1990. Enfin, nous présentons nos résultats dans le cadre de la coloration de carrés, où il s'agit de colorier les sommets sans qu'il y ait deux sommets adjacents ou avec un voisin commun qui soient de la même couleur. On s'intéresse en particulier à des conditions suffisantes sur la densité du graphe (c-à-d le degré moyen maximum d'un sous-graphe) pour qu'on puisse colorier son carré avec peu de couleurs. / This thesis falls within graph theory, and deals more precisely with graph coloring problems. In this thesis, we use and develop the discharging method, a counting argument that makes strong advantage of the graph structure. This method is decisive in the proof of the Four Color Theorem. We first give an illustrated overview of the discharging tools that are used for this work: nice methods that we apply, and handy tricks that we develop. In the realm of list edge coloring, we most notably prove that the weak List Coloring Conjecture is true for planar graphs of maximum degree 8 (i.e. that they are edge 9-choosable), thus improving over a result of Borodin from 1990. We finally present our results about square coloring, where the goal is to color the vertices in such a way that two vertices that are adjacent or have a common neighbor receive different colors. We look in particular into sufficient conditions on the density of a graph (i.e. the maximum average degree of a subgraph) for its square to be colorable with few colo

Cette thèse aborde le problème de la surcharge des réseaux des données des opérateurs mobiles. La croissance des abonnements au haut débit mobile engendre aujourd'hui de nombreux goulots d'étranglement dans ces réseaux. Plus particulièrement, la disponibilité de la bande passante sur les stations de bases est de plus en plus réduite. Pour faire face à cette problématique, les opérateurs mobiles essaient de décharger le trafic des données de leurs infrastructures en déployant des réseaux de substitution à petites cellules, tels que les femtocells ou réseaux WiFi publics. Ces réseaux restent néanmoins très localisés et ne résolvent donc que très partiellement le problème. Ainsi, plus récemment, nous voyons l'émergence des réseaux opportunistes qui visent à transmettent les données en ne se basant que sur les dispositifs mobiles, c-à-d, de dispositif à dispositif. Cette thèse vise à évaluer la faisabilité de décharger le trafic de données mobile à l'aide des hotspots WiFi en étendant leur champs de couverture par l'utilisation des réseaux opportunistes. Pour ce faire, cette thèse propose un cadre pour le déchargement (offloading) de données de façon opportuniste et un mécanisme d'incitation pour encourager la coopération des utilisateurs des dispositifs mobiles. Dans une première partie de cette thèse, nous avons tracé la couverture 3G et WiFi à travers plusieurs lignes de bus à Paris afin d'évaluer la façon dont les utilisateurs et les opérateurs mobiles peuvent bénéficier des réseaux WiFi existants pour le déchargement des données. Nos résultats indiquent que les points d'accès WiFi déployés par les fournisseurs de service Internet peuvent décharger une partie non négligeable du trafic de données, cependant des restrictions telles que le temps de l'association et le processus d'authentification peuvent diminuer la quantité de données transmises. Dans une tentative d'offrir une nouvelle approche pour le déchargement mobile, nous proposons dans un second temps un cadre décisionnel multi-critères, appelé OppLite, pour décharger les données des réseaux de mobiles 3G grâce à des communications dispositif à dispositif opportunistes. Nous avons montré par des simulations qu'un tel déchargement mobile opportuniste peut étendre la couverture et l'efficacité des réseaux cellulaires, permettant un déchargement pouvant aller jusqu'à 36% des données dans certains scénarios. L'efficacité du déchargement mobile par les réseaux opportunistes dépend principalement de la tolérance au délai par l'application et de la coopération des utilisateurs mobiles. Le déchargement opportuniste dépend de la volonté de l'utilisateur d'offrir ses ressources aux autres. Nous avons donc proposé, dans un troisième temps, un mécanisme d'incitation, appelé MINEIRO, qui calcul un rang de réputation basée sur la source des messages reçus par les nœuds intermédiaires. MINEIRO permet à des réseaux composés d'un pourcentage important, allant jusqu'à 60%, de nœuds avec un comportement égoïste sans dégradation des performances dans un scénario de mobilité aléatoire. Au delà de ce pourcentage, MINEIRO permet maintenir un taux de livraison et des délais de livraison constants / This thesis addresses the overload problem of the Wireless Internet service Providers' (WISP) network. The growth of mobile broadband subscription has been leading several bottlenecks to WISPs, such as, bandwidth availability and resource sharing of over a single cellular cell. WISPs can move off data traffic from its infrastructure by deploying small cells, such as femtocells, to public WiFi networks or, more recently, to device-to-device opportunistic networks. This work evaluates the feasibility to offload mobile data traffic using WiFi hotspots, proposes a framework to opportunistic data offloading and an incentive mechanism to encourage users cooperation. We mapped 3G and WiFi coverage through several bus routes in Paris in order to evaluate how users and WISPs can benefit from the existing infrastructure. Our results indicate that the deployed WISPs access points can offload part of the data traffic, however restrictions such as association time and the authentication process may reduce the amount of offloaded data. We propose a multi-criteria decision-making framework, called OppLite, to offload data from 3G networks using opportunistic device-to-device communications. Trace-driven simulations showed that opportunistic mobile offloading can expand coverage and network efficiency, offloading up to 36% of data in certain scenarios. Thus, the effectiveness of opportunistic mobile offloading depends mainly of the delay tolerance of the applications and whether the user cooperates. Since opportunistic offloading depends on the user's willingness to offer his/her resources to others, we propose a message-based incentive mechanism that builds a reputation rank based on the source of messages received by the forwarding nodes, called MINEIRO. The network supports up to 60% of nodes with selfish behavior without performance degradation in a random mobility scenario. After this threshold, MINEIRO kept the delivery rate and the delay constant. Meanwhile, in a scenario with social-based mobility, selfish behavior degrades the network performance quickly

Les techniques polyédriques permettent d’appliquer des analyses et transformations de code sur des structures multidimensionnelles telles que boucles imbriquées et tableaux. Elles sont en général restreintes aux programmes séquentiels dont le contrôle est affine et statique. Cette thèse consiste à les étendre à des programmes comportant par exemple des tests non analysables ou exprimant du parallélisme. Le premier résultat est l'extension de l’analyse de durée de vie et conflits mémoire, pour les scalaires et les tableaux, à des programmes à spécification parallèle ou approximée. Dans les travaux précédents sur l’allocation mémoire pour laquelle cette analyse est nécessaire, la notion de temps ordonne totalement les instructions entre elles et l’existence de cet ordre est implicite et nécessaire. Nous avons montré qu'il est possible de mener à bien de telles analyses sur un ordre partiel quelconque qui correspondra au parallélisme du programme étudié. Le deuxième résultat est d'étendre les techniques de repliement mémoire, basées sur les réseaux euclidiens, de manière à trouver automatiquement une base adéquate à partir de l'ensemble des conflits mémoire. Cet ensemble est fréquemment non convexe, cas qui était traité de façon insuffisante par les méthodes précédentes. Le dernier résultat applique les deux analyses précédentes au calcul par blocs "pipelinés" et notamment au cas de blocs de taille paramétrique. Cette situation donne lieu à du contrôle non-affine mais peut être traité de manière précise par le choix d’approximations adaptées. Ceci ouvre la voie au transfert efficace de noyaux de calculs vers des accélérateurs tels que GPU, FPGA ou autre circuit spécialisé. / Polyhedral techniques enable the application of analysis and code transformations on multi-dimensional structures such as nested loops and arrays. They are usually restricted to sequential programs whose control is both affine and static. This thesis extend them to programs involving for example non-analyzable conditions or expressing parallelism. The first result is the extension of the analysis of live-ranges and memory conflicts, for scalar and arrays, to programs with parallel or approximated specification. In previous work on memory allocation for which this analysis is required, the concept of time provides a total order over the instructions and the existence of this order is an implicit requirement. We showed that it is possible to carry out such analysis on any partial order which match the parallelism of the studied program. The second result is to extend memory folding techniques, based on Euclidean lattices, to automatically find an appropriate basis from the set of memory conflicts. This set is often non convex, case that was inadequately handled by the previous methods. The last result applies both previous analyzes to "pipelined" blocking methods, especially in case of parametric block size. This situation gives rise to non-affine control but can be processed accurately by the choice of suitable approximations. This paves the way for efficient kernel offloading to accelerators such as GPUs, FPGAs or other dedicated circuit.

Cette thèse présente des résultats obtenus dans deux domaines : la théorie des langages, et la théorie des graphes. En théorie des langages, on s’intéresse à des problèmes de caractérisation de classes de langages réguliers. Le problème générique consiste à déterminer si un langage régulier donné peut être défini dans un certain formalisme. Les méthodes actuelles font intervenir un problème plus général appelé séparation. On présente ici deux types de contributions : une généralisation d’un résultat de décidabilité au cadre des langages de mots infinis, ainsi que des bornes inférieures pour la complexité du problème de séparation. En théorie des graphes, on considère le problème classique de coloration de graphes, où on cherche à attribuer des couleurs aux sommets d’un graphe de sorte que les sommets adjacents reçoivent des couleurs différentes, le but étant d’utiliser le moins de couleurs possible. Dans le cas des graphes peu denses, la méthode de déchargement est un atout majeur. Elle a notamment joué un rôle décisif dans la preuve du théorème des quatre couleurs. Cette méthode peut être vue comme une construction non conventionnelle d’un schéma de preuve par induction, spécifique à la classe de graphes et à la propriété considérées, et où la validité du schéma est rarement immédiate. On utilise des variantes de la méthode de déchargement pour étudier deux types de problèmes de coloration. / In this thesis, we present results obtained in two fields: formal language theory and graph theory. In formal language theory, we consider some problems of characterization of classes of regular languages. The generic problem consists in determining whether a given regular language can be defined in a fixed formalism. The current approaches use a more general problem called separation. We present here two types of contributions: a generalization of a decidability result to the setting of infinite words, together with lower bounds for the complexity of the separation problem. In graph theory, we consider the classical problem of graph coloring, where we assign colors to vertices of a graph in such a way that two adjacent vertices receive different colors. The goal is to use the fewest colors. When the graphs are sparse, a crucial tool for this is the discharging method. It is most notably decisive in the proof of the Four-Color Theorem. This method can be seen as an unconventional construction of an inductive proof scheme, specific to the considered problem and graph class, where arguing the validity of the scheme is rarely immediate. We use variants of the discharging method to study two types of coloring problems.

De nos jours, le transport de marchandise occupe une place importante dans la vie économique des sociétés modernes. Le problème de collecte et de distribution avec fenêtres de temps à un seul véhicule est un des problèmes les plus rencontrés. Ayant un ensemble de demandes à satisfaire, le véhicule doit transporter des biens de fournisseurs à leurs clients respectifs en respectant les fenêtres de temps et sa capacité. Dans ce travail, nous présentons un état de l'art du 1-PDPTW et nous proposons plusieurs approches évolutionnistes pour traiter ses deux cas : statique et dynamique. Nos approches utilisent principalement des algorithmes évolutionnistes basés sur l'utilisation d'opérateurs génétiques spéciaux conçus dans le but d'améliorer la qualité des solutions et de diminuer le temps de calcul. Elles sont aussi basées sur la Pareto optimalité pour fournir un ensemble de solutions viables. Quelques unes de nos approches utilisent des bornes inférieures de distance et de retard dans le but d'évaluer les résultats obtenus. Une recherche Tabou, constituant un étage d'hybridation, peut être appliquée pour l'amélioration des solutions obtenues par les algorithmes évolutionnistes. Enfin nous présentons quelques simulations et résultats élaborés à partir de benchmarks spécialement conçus pour le 1-PDPTW ainsi que d'autres provenant de la littérature.

De nombreux procédés industriels nécessitent la manipulation de matériaux sous forme pulvérulente. L’émission de poussières générée par leur manipulation peut s’avérer dangereuse pour la santé des travailleurs ou bien causer un risque d’explosion. Afin de mieux comprendre les mécanismes de dispersion des poussières, le cas de la décharge d’un silo est étudié par simulation numérique avec une approche Euler-Euler. Deux configurations ont été étudiées au cours de cette thèse. La première, sans silo, a permis d’étudier l’influence de perturbations de vitesses imposées à l’entrée de la chambre de dispersion en lieu et place du silo. Cette étude a révélé que ces perturbations peuvent influencer l’élargissement du panache de poudre. Seules les perturbations avec une corrélation temporelle ont généré une ouverture importante du jet tombant semblable à celle relevée expérimentalement. Dans la deuxième configuration, le silo et la chambre de dispersion sont représentés afin d’étudier le couplage entre la dispersion du jet et l’écoulement dans le silo. L’une des difficultés de ces simulations est de prédire les différents régimes d’écoulements granulaires, allant de l’état quasi-statique dans le silo au régime très dilué lors de la dispersion du jet tombant, en passant par le régime collisionnel à la sortie du silo. La théorie cinétique permet de modéliser le régime dilué et collisionnel. En revanche pour la partie quasi-statique un modèle semi-empirique a été utilisé, implémenté et validé sur différentes configurations. La seconde étude a montré l’importance du rapport entre le diamètre de l’orifice et le diamètre des particules sur la structure du jet. En effet, lorsque ce paramètre est faible, le coeur du jet se contracte immédiatement après la sortie du silo puis s’ouvre en aval. Pour des valeurs grandes, l’ouverture du jet est négligeable. Cependant, il semblerait que l’angle du silo modifie le comportement de l’écoulement, ce qui nécessitera des études supplémentaires. / A wide range of industrial processes requires the handling of granular material in a pulverulent form. The subsequent dust emissions due to these processes can be harmful to the health of workers or hazardous explosion risks. In order to understand dust dispersion mechanisms, a case of a free falling granular jet discharged from a silo is studied by numerical simulations using an Euler-Euler approach. Two types of numerical simulation are conducted. First, the influence of velocity fluctuations at the inlet chamber is studied on the plume behavior, instead of the silo. This study reveals that fluctuations are enable to reproduce the jet expansion. It is established that only fluctuations with temporal correlation generate a large jet opening similar to the experiment. The second type of setup shows the coupling between the silo and the chamber. One of the major challenges is the ability to predict the different flow regimes going from quasi-static regime inside the silo, to the very dilute regime in the dust spread and include the collisional regime occurs through the silo. Kinetic theory allows modeling of the dilute and collisional regime. By contrast, frictional models have been used, implemented and validated in different cases. The second study highlights the key role of the ratio defined by the orifice diameter on the particle diameter. Indeed, when this parameter is small, the jet powder core contracts immediately after the exit of the silo dump plane and expands downstream. For high values, the granular jet does not exhibit dispersion anymore. This study suggests that the silo half-angle has an impact on the flow field which justifies the need for further investigations.

La terre compactée est considérée comme un mélange granulaire dans lequel l'argile joue un rôle de liant mais cette dernière exhibe une forte interaction avec l'eau. Pendant la durée de vie en service, la terre compactée est soumise aux changements de l’humidité relative. En raison de ces changements des conditions ambiantes perpétuels, la teneur en eau dans la terre varie, impactant leur performance mécanique. Le présent travail a ainsi pour but d’étudier l’impact de l’humidité relative et de la teneur d'argile sur le comportement mécanique de la terre compactée. Il se réalisera au travers d’études expérimentales et d'une modélisation constitutive. Dans la première partie de cette thèse, quatre terres régionales de provenances et de teneurs d'argile différentes sont identifiées. Une étude comparative a été réalisée entre le double compactage statique et le compactage dynamique. En parallèle, trois types d'essais spécifiques : essais de succion par la méthode de papier-filtre, essais de retrait et essais d'absorption d'eau, ont été menés pour donner des indications préliminaires quant aux effets d'interaction entre l'eau et l'argile. Dans la deuxième partie, l’impact de l’humidité relative et de la teneur d'argile sur le comportement de cisaillement a été étudié, prenant en compte des cycles de chargement-déchargement. En adoptant une définition particulière de la contrainte effective de Bishop, il a également été observé que les états de rupture dans le plan (p'-q) pour tous les échantillons sont alignés approximativement à une ligne droite unique passant par l'origine, quelque soit la succion et la pression de confinement. Sur la base des résultats expérimentaux, un nouveau modèle constitutif a été développé pour la simulation du comportement mécanique de la terre compactée. Ce nouveau modèle a ainsi été formulé dans la cadre de la mécanique de l'endommagement des milieux continus et de la théorie de Bounding Surface Plasticity. / Compacted earth is regarded as a granular mixture in which clay plays a role of binder but it also exhibits an important interaction with water. During their service life, compacted earth can be subject to large changes in relative humidity. Those perpetual changes of environmental conditions induce continuous changes of water content of the earth that impact significantly its mechanical performances. The present work aimes at studying the mechanical behavior of compacted earth with respect to relative humidity and clay content. It involves an extensive experimental study and a constitutive modelling. In the first part of this thesis, four kinds of local earth are identified with different clay contents. A comparison of compaction method was then conducted between a double static compaction and dynamic compaction. Three types of specific tests: suction test by filter paper method, shrinkage test and sorption-desorption test were carried out, thereby providing a preliminary insight on the interaction effects between clay and water. In the second part, the impact of clay and moisture contents on the shear behavior of compacted earth was investigated taking into account loading-unloading cycles. Adopting a particular definition of Bishop's effective stress, failure states of all samples were observed to lie approximately on a unique failure line crossing the origin in the (p'-q) plane regardless of matric suction and confining pressure. Finally, based on the above experimental results, a new constitutive model was proposed, based on the theories of Bounding Surface Plasticity and continuum damage mechanics, aiming to simulate mechanical behaviour of compacted earth.

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques. La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum est n − 1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour la cardinalité du code identifiant minimum dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ce paramètre dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits.

La logistique inverse des déchets techniques encombrants de type blanc ou brun se développe de nos jours afin de répondre aux contraintes législatives fortes qui n'autorisent à partir de juillet 2002 que la mise en décharge des déchets dits « ultimes ». Le recyclage noble apparaît comme une solution prometteuse, économiquement viable et écologique, où la collecte, approvisionneuse exclusive du processus de récupération des déchets, doit être appréhendée et planifiée dans l'objectif de maîtrise des coûts. Après avoir identifié les caractéristiques principales des systèmes de collecte existants, nous nous attardons sur le ramassage à domicile des produits usagés de la population. Afin de pouvoir établir une planification opérationnelle, ce mode de collecte est modélisé comme un problème de routage de véhicules : le problème de chargement et de déchargement avec contraintes de fenêtres temporelles, de précédence et de capacité. Ce problème d'Optimisation Combinatoire est ensuite résolu de manière algorithmique, en considérant successivement le cas d'un véhicule, puis de plusieurs véhicules. La résolution du problème se base sur la recherche tabou et la recherche tabou probabiliste, et fournit des résultats très satisfaisants sur le plan qualitatif et en temps d'exécution. Finalement, nous décrivons, grâce au langage de modélisation unifié orienté objet UML, une manière d'intégrer nos résultats algorithmiques dans un module d'aide à la décision pour la planification opérationnelle de la collecte, où l'opérateur humain est chargé de définir le plan de collecte à exécuter.

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques.La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum ID est n-1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour le paramètre ID dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ID dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits. / In this thesis we study three theoretical computer science problems, namely the orthogonal packing problem (OPP for short), strong edge-colouring and identifying codes.OPP consists in testing whether a set of rectangular items can be packed in a rectangular container without overlapping and without exceeding the borders of this container. An additional constraint is that the rotation of the items is not allowed. The problem is NP-hard even when the problem is reduced to packing squares in a square. We propose an exact algorithm for solving OPP efficiently using the characterization of the problem by interval graphs proposed by Fekete and Schepers. For this purpose we use some compact representation of interval graphs - MPQ-trees. We show experimental results of our approach by comparing them to the results of other algorithms known in the literature. we observe promising gains.The study of strong edge-colouring and identifying codes is focused on the structural and computational aspects of these combinatorial problems. In the case of strong edge-colouring we are interested in the families of planar graphs and subcubic graphs. We show optimal upper bounds for the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also show that every planar subcubic graph without induced cycles of length 4 and 5 can be strong edge-coloured with at most nine colours. Finally, we confirm the difficulty of the problem by showing that it remains NP-complete even in some restricted classes of planar subcubic graphs.For the subject of identifying codes we propose a characterization of non-trivial graphs having maximum identifying code number ID, that is n-1, where n is the number of vertices. We study the case of line graphs and prove lower and upper bounds for ID parameter in this class. At last we investigate the complexity of the corresponding decision problem and show the existence of a linear algorithm for computing ID of the line graph L(G) where G has the size of the tree-width bounded by a constant. On the other hand, we show that the identifying code problem is NP-complete in various subclasses of planar graphs.