L’affectation de fr´equences (AFP) consiste `a attribuer des fr´equences radio aux liens de communications d’un r´eseauen respectant un spectre de fr´equences donn´e et des contraintes d’interf´erence ´electromagn´etique sur les liens. Vu lalimitation des ressources spectrales pour chaque application, les ressources en fr´equences sont souvent insuffisantespour d´eployer un r´eseau sans interf´erence. Dans ce cas, le r´eseau est surcontraint et le probl`eme est irr´ealisable.R´esoudre le probl`eme consiste alors `a identifier les zones surcontraintes pour en revoir la conception.Le travail que nous pr´esentons concerne la recherche d’une de ces zones surcontraintes avec une approche algo-rithmique bas´ee sur la mod´elisation du probl`eme par un CSP. Le probl`eme de l’affectation de fr´equences doit doncˆetre mod´elis´e comme un probl`eme de satisfaction de contraintes (CSP) qui est repr´esent´e par un tripl´e : un ensemblede variables (les liens radio), un ensemble de contraintes (les interf´erences ´electromagn´etiques), et un ensemble dedomaines (les fr´equences admises).Sous forme de CSP, une zone perturb´ee peut ˆetre consid´er´ee comme un sous-ensemble irr´ealisable irr´eductible duprobl`eme (IIS pour Irreductible Infeasible Subset). Un IIS est un sous probl`eme de taille minimale qui est irr´ealisable,c’est-`a-dire que tous les sous-ensembles d’un IIS sont r´ealisables. L’identification d’un IIS dans un CSP se rapporte `a deux r´esultats g´en´eraux int´eressants. Premi`erement, en localisant un IIS on peut plus facilement prouver l’irr´ealisabilit´ed’un probl`eme donn´e car l’irr´ealisabilit´e d’un IIS, qui est suppos´e ˆetre petit par rapport au probl`eme complet, est plusrapidement calculable que sur le probl`eme entier. Deuxi`emement, on peut localiser la raison de l’irr´ealisabilit´e; dansce cas, sur un probl`eme r´eel, le d´ecideur peut proposer des solutions pour relˆacher des contraintes de l’IIS, et peut-ˆetre aboutir `a une solution r´ealisable pour son probl`eme. La recherche d’IIS consiste donc `a r´esoudre un probl`emefondamental qui fait partie des outils de prise de d´ecision.Ce travail propose des algorithmes pour identifier un IIS dans un CSP incoh´erent. Ces algorithmes ont ´et´e test´essur des instances connues du probl`eme de l’affectation des fr´equences et du probl`eme de k-coloration de graphe. Lesr´esultats ont montr´es d’une grande am´elioration sur des instances du probl`eme de l’affectation des fr´equences parrapport aux m´ethodes connues. / The frequency assignment (FAP) consists in assigning the frequency on the radio links of a network which satisfiesthe electromagnetic interference among the links. Given the limited spectrum resources for each application, the fre-quency resources are often insufficient to deploy a wireless network without interference. In this case, the network isover-contrained and the problem is infeasible. Our objective is to identify an area with heavy interference.The work presented here concerns the detection for one of these areas with an algorithmic approach based onmodeling the problem by CSP. The problem of frequency assignment can be modeled as a constraint satisfactionproblem (CSP) which is represented by a triple: a set of variables (radio links), a set of constraints (electromagneticinterference) and a set of available frequencies.The interfered area in CSP can be considered a subset of irreducible feasible subset (IIS). An IIS is a infeasiblesubproblem with irreducible size, that is to say that all subsets of an IIS are feasible. The identification of an IIS ina CSP refers to two general interests. First, locating an IIS can easily prove the infeasibility of the problem. Becausethe size of IIS is assumed to be smaller compared to the entire problem, its infeasibility is relatively easier to prove.Second, we can locate the reason of infeasibility, in this case, the decision maker can provide the solutions to relax theconstraints inside IIS, which perhaps leads to a feasible solution to the problem.This work proposes algorithms to identify an IIS in the over-constrained CSP. These algorithms have tested on the well known benchmarks of the FAP and of the problem of graph k-coloring. The results show a significant improve-ment on instances of FAP compared to known methods.

Le problème de coloration de graphe est un problème NP-complet particulièrement étudié, qui permet de modéliser de problèmes dans des domaines variés. Dans cette thèse, de nouveaux algorithmes exacts basés sur une étude de la structure du graphe sont proposés. Ce travail s'appuie sur l'algorithme « Total solutions Exact graph Coloring » (TexaCol) qui construit toutes les solutions en exploitant l'ensemble des cliques d'un graphe. Deux algorithmes exacts, « Partial best solutions Exact graph Coloring » (PexaCol) et « All best solutions Exact graph Coloring » (AexaCol), sont présentés ici pour construire certaines solutions optimales ou toutes les meilleures solutions. Ces deux algorithmes utilisent la méthode de backtracking, dans laquelle ils ne choisissent que les sous-ensembles de meilleurs solutions pour continuer la coloration. L’analyse de résultat montre que PexaCol et AexaCol sont capables de traiter des graphes plus grands que TexaCol. Mais surtout, AexaCol trouve toutes les meilleures solutions significativement plus vite que TexaCol ainsi que le solveur Gurobi, qui sont utilisés comme référence.La téléphonie mobile est un domaine en plein essor qui peut s'appuyer sur une modélisation à base de graphes. Actuellement, les techniques de type « Device-to-Device » (D2D) prennent une place importante dans les réseaux mobiles. L’allocation de ressource constitue l'un des principaux problèmes en matière de performance. Pour assigner efficacement une ressource radio à une paire D2D dans le système Long-Term Evolution (LTE), un schéma systématique d'allocation de ressources est proposé dans cette thèse. Il est basé sur une clusturisation des liens D2D, et permet de prendre en compte à la fois l'allocation inter-cluster et intra-cluster des ressources. En déterminant les zones d'interférence, le problème d'allocation des ressources inter-cluster est formulé comme un problème de coloration de graphe dynamique. Un algorithme de coloration de graphe dynamique est ainsi proposé, basé sur PexaCol. Cet algorithme peut assigner les ressources radio aux clusters qui sont générés ou supprimés dynamiquement. L’analyse numérique montre que cet algorithme assure une bonne performance en termes d'utilisation des ressources, de temps d’exécution et d'adaptabilité. Concernant le problème d’allocation de ressources inter-cluster, une méthode fondée sur la topologie est proposée, intégrant naturellement l'allocation de puissance et l’allocation de Resource Block (RB). Pour simplifier ce problème d'allocation de ressources, la meilleure topologie est choisie à chaque étape, celle qui permet d'obtenir le meilleur débit en utilisant le moins de RBs. A partir de ce procédé, quatre algorithmes d'optimisation sont proposés: l’algorithme glouton statique, PexaCol statique, PexaCol dynamique et PexaCol dynamique approximatif. L'analyse des résultats montre que pour les petits clusters, les versions statiques et dynamiques de PexaCol permettent d'obtenir un index d’optimisation maximal en choisissant la meilleure topologie locale pour chaque noeud. A l'opposé, les algorithmes "glouton statique" et "PexaCol dynamique approximatif" permettent d'obtenir une solution sous-optimale pour l'optimisation locale avec une complexité moindre. Pour les grands clusters, avec certaine séquence de la coloration, le PexaCol dynamique approximatif est mieux que l’algorithme glouton statique pour l’index d’optimisation pendant un temps d’exécution acceptable. / Graph coloring problem is a famous NP-complete problem, which has extensive applications. In the thesis, new exact graph coloring algorithms are researched from a graph structure point of view. Based on Total solutions Exact graph Coloring algorithm (TexaCol) which is capable of getting all coloring solution subsets for each subgraph, two other exact algorithms, Partial best solutions Exact graph Coloring algorithm (PexaCol) and All best solutions Exact graph Coloring algorithm (AexaCol), are presented to get multiple best solutions. These two algorithms utilize the backtracking method, in which they only choose the best solution subset each step to continue the coloring until partial or all best solutions are obtained. The result analysis shows that PexaCol and AexaCol can deal with larger graphs than TexaCol and especially, AexaCol runs much faster than TexaCol and the solver Gurobi to get all best solutions.Device-to-Device (D2D) is a promising technique for the future mobile networks, such as 5th generation wireless systems (5G), and the resource allocation is one of the most crucial problems for its performance. In order to efficiently allocate radio resource for D2D links in Long-Term Evolution (LTE) system, a systematic resource allocation scheme is proposed based on D2D clusters, including the inter-cluster resource allocation and the intra-cluster resource allocation. With the cluster interference range, the inter-cluster resource allocation problem is formulated as a dynamic graph coloring problem, and a dynamic graph coloring algorithm is designed based on PexaCol. This algorithm is able to allocate radio resource to clusters while they are dynamically generated and deleted. The numerical analysis results show that this algorithm has good performance in resource utilization, runtime and scalability.For the intra-cluster resource allocation problem, a topology-based resource allocation method is designed naturally combining power allocation with Resource Block (RB) allocation. To simplify this associated optimization problem, a local optimal method is proposed, in which the best topology is chosen each step achieving the maximal throughput with the minimum number of assigned RBs. With respect to this method, four algorithms are presented: static greedy, static PexaCol, dynamic PexaCol and dynamic PexaCol approximate. Result analysis shows that for small-scale clusters, static PexaCol and dynamic PexaCol are capable of getting a maximal optimization index by locally choosing the best topology for each node while static greedy and dynamic PexaCol approximate are able to get the suboptimal solution for the local optimization with much lower complexity. For large-scale clusters, giving certain treating sequences, the dynamic PexaCol approximate performs better than static greedy regarding the optimization index within an acceptable runtime.

La coloration de graphes est un problème central de l’optimisation combinatoire. C’est un domaine très attractif par ses nombreuses applications. Différentes variantes et généralisations du problème de la coloration de graphes ont été proposées et étudiées. La coloration d’arêtes d’un graphe consiste à attribuer une couleur à chaque arête du graphe de sorte que deux arêtes ayant un sommet commun n’ont jamais la même couleur, le tout en utilisant le moins de couleurs possibles. Dans la première partie de cette thèse, nous étudions le problème de la coloration d’arêtes ℓ-distance, qui est une généralisation de la coloration d’arêtes classique. Nous menons une étude combinatoire et algorithmique du paramètre. L’étude porte sur les classes de graphes suivantes : les chaines, les grilles, les hypercubes, les arbres et des graphes puissances. Le paramètre de la coloration d’arêtes ℓ-distance permet de modéliser des problèmes dans des réseaux assez grands. Cependant, avec la multiplication du nombre de nœuds, les réseaux sont de plus en plus vulnérables aux défaillances (ou pannes). Dans la deuxième partie, nous nous intéressons aux algorithmes tolérants aux pannes et en particulier les algorithmes auto-stabilisants. Nous proposons un algorithme auto-stabilisant pour la coloration propre d’arêtes. Notre solution se base sur le résultat de vizing pour utiliser un minimum de couleurs possibles. Par la suite, nous proposons un algorithme auto-stabilisant de clustering destine a des applications dans le domaine de la sécurité dans les réseaux mobiles Ad hoc. La solution que nous proposons est un partitionnement en clusters base sur les relations de confiance qui existent entre nœuds. Nous proposons aussi un algorithme de gestion de clés de groupe dans les réseaux mobiles ad hoc qui s’appuie sur la topologie de clusters préalablement construite. La sécurité de notre protocole est renforcée par son critère de clustering qui surveille en permanence les relations de confiance et expulse les nœuds malveillants de la session de diffusion. / Graph coloring is a famous combinatorial optimization problem and is very attractive for its numerous applications. Many variants and generalizations of the graph-coloring problem have been introduced and studied. An edge-coloring assigns a color to each edge so that no two adjacent edges share the same color. In the first part of this thesis, we study the problem of the ℓ-distance-edge-coloring, which is a generalization of the classical edge-coloring. The study focuses on the following classes of graphs : paths, grids, hypercubes, trees and some power graphs. We are conducting a combinatorial and algorithmic study of the parameter. We give a sequential coloring algorithm for each class of graph. The ℓ-distance-edge-coloring is especially considered in large-scale networks. However, with the increasing number of nodes, networks are increasingly vulnerable to faults. In the second part, we focus on fault-tolerant algorithms and in particular self-stabilizing algorithms. We propose a self-stabilizing algorithm for proper edge-coloring. Our solution is based on Vizing’s result to minimize number of colors. Subsequently, we propose a selfstabilizing clustering algorithm for applications in the field of security in mobile ad hoc networks. Our solution is a partitioning into clusters based on trust relationships between nodes. We also propose a group key-management algorithm in mobile ad hoc networks based on the topology of clusters previously built. The security of our protocol is strengthened by its clustering criterion which constantly monitors trust relationships and expels malicious nodes out of the multicast session.

In this thesis, we consider wireless ad hoc and sensor networks where energy matters. Indeed, sensor nodes are characterized by a small size, a low cost, an advanced communication technology, but also a limited amount of energy. This energy can be very expensive, difficult or even impossible to renew. Energy efficient strategies are required in such networks to maximize network lifetime. We distinguish four categories of strategies: 1. Energy efficient routing, 2. Node activity scheduling, 3. Topology control by tuning node transmission power and 4. Reduction of the volume of information transferred. Our contribution deals with energy efficient routing and node activity scheduling. For energy efficient routing, the idea consists in reducing the energy spent in the transmission of a packet from its source to its destination, while avoiding nodes with low residual energy. The solution we propose, called EOLSR, is based on the link state OLSR routing protocol. We show by simulation that this solution outperforms the solution that selects routes minimizing the end-to-end energy consumption, as well as the solution that builds routes based on node residual energy. We then show how we can improve the benefit of energy efficient routing using cross layering. Informa- tion provided by the MAC layer improves the reactivity of the routing protocol and the robustness of routes. Moreover, taking into account the specificities of some applications like data gathering allows the routing protocol to reduce its overhead by maintaining routes only to the sink nodes. Concerning node activity scheduling, since the sleep state is the least power consuming state, our aim is to schedule node state between sleeping and active to minimize energy consumption while ensuring network and application functionalities. We propose a solution, called SERENA, based on node coloring. The idea is to assign a color to each node, while using a small number of colors and ensuring that two nodes with the same color can transmit without interfering. This color is mapped into a slot in which the node can transmit its messages. Consequently, each node is awake during its slot and the slots granted to its one-hop neighbors. It sleeps the remaining time. We show how this algorithm can adapt to different application requirements: broadcast, immediate acknowledgement of unicast transmissions... The impact of each additional requirement is evaluated by simulation. An originality of this work lies in taking into account real wireless propagation conditions. Color conflicts are then possible. A cross-layering approach with the MAC layer is used to solve these conflicts. We also show how cross-layering with the application layer can improve the coloring per- formance for data gathering applications. This work has been done for the ANR OCARI project whose aim is to design and implement a wireless sensor network for applications in harsh environments such as power plants and war- ships. The network layer including SERENA and EOLSR has been specified and is now under implementation.

A coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices are given the same color. The chromatic number of a graph is the least number of colors needed to color all of its vertices. Graph coloring problems can be applied to many real world applications, such as scheduling and register allocation. Computationally, the decision problem of whether a general graph is m-colorable is NP-complete for m ≥ 3. The graph studied in this thesis is a well-known combinatorial object, the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for all k; however, coloring the square of the cube is a much more interesting problem. This is the graph in which the vertices are binary vectors of length k, and two vertices are adjacent if and only if the Hamming distance between the two vectors is at most 2. Any color class in a coloring of Q2k is a binary (k;M, 3) code. This thesis will begin with an introduction to binary codes and their structure. One of the most fundamental combinatorial problems is finding optimal binary codes, that is, binary codes with the maximum cardinality satisfying a specified length and minimum distance. Many upper and lower bounds have been produced, and we will analyze and apply several of these. This leads to many interesting results about the chromatic number of the square of the cube. The smallest k for which the chromatic number of Q2k is unknown is k = 8; however, it can be determined that this value is either 13 or 14. Computational approaches to determine the chromatic number of Q28 were performed. We were unable to determine whether 13 or 14 is the true value; however, much valuable insight was learned about the structure of this graph and the computational difficulty that lies within. Since a 13-coloring of Q28 must have between 9 and 12 color classes being (8; 20; 3) binary codes, this led to a thorough investigation of the structure of such binary codes.

The aim of this work is to understand the requirements behind Quality of Service (QoS) for Multihop Wireless Networks and evaluate the performance of different such strategies. This work starts by establishing the basis for requirement of QoS and evaluates different approaches for providing QoS. Bandwidth is selected as the most important resource amongst the resources identified for ensuring QoS. The problem is modeled as an optimization problem that tries to maximize the amount of bandwidth available in the system while providing bounds over the bandwidth available over a route. Other QoS parameters are bound by hard limits and are not involved in the optimization problem. The existence of spatial reuse rules has been established through simulations for a TCP based network. This establishes that the reuse rules are independent of the MAC and network layer protocols used. This idea is used in designing the simulations for strategies that use controlled spatial reuse and give known bounds for QoS. Simulations take the network and a set of connections to generate the best possible schedule that guarantees bandwidth to individual connections and maximizes the total number of slots used in the entire system. The total number of slots used is a measure of the bandwidth in use. The set of graphs and connections is generated by a random graph and connection generator and the data set is large enough to average the results. There are two different approaches used for scheduling the connections. The first approach uses graph coloring and provides a simpler implementation in terms of network deployments. Second approach uses on-demand slot allocation. The approaches are compared for their pros and cons. The first approach uses graph coloring to allocate fixed number of slots to each link. This makes an equivalent of a wired network with fixed bandwidth over each link. This network is simpler to operate and analyze at the cost of one time expense of graph coloring. The assumption here is that the network is static or has low mobility. The on demand approach is more flexible in terms of slot assignment and is adaptable to the changing traffic patterns. The cons are that connection establishment is more expensive in terms of bandwidth required and is more complicated and difficult to analyze. The advantages include low initial network establishment cost and accommodation of mobility.

Στα πλαίσια της διατριβής αναπτύξαμε δύο από τους πρώτους αλγορίθμους υπολογισμού μιας ε-προσεγγιστικής ισορροπίας Nash για την περίπτωση όπου το ε είναι κάποια σταθερά. Οι προσεγγίσεις που επιτυγχάνουν οι αλγόριθμοί μας είναι ε=3/4 και ε=(2+λ)/4 αντίστοιχα, όπου λ είναι το ελάχιστο, μεταξύ όλων των ισορροπιών Nash, κέρδος για έναν παίκτη. Επιπλέον, μελετήσαμε μια ευρεία κλάση τυχαίων παιγνίων δύο παικτών, για την οποία υπολογίσαμε μια πολύ καλή ε-προσεγγιστική ισορροπία Nash, με το ε να τείνει στο 0 καθώς το πλήθος των διαθέσιμων στρατηγικών των παικτών τείνει στο άπειρο. Οι αρχές της θεωρίας παιγνίων είναι χρήσιμες στην ανάλυση της επίδρασης που έχει στην καθολική απόδοση ενός συστήματος διαμοιραζόμενων πόρων η εγωιστική και ανταγωνιστική συμπεριφορά των χρηστών του. Προς την κατεύθυνση αυτή, εστιάσαμε στο πρόβλημα της εξισορρόπησης φορτίου. Μελετήσαμε διάφορα μοντέλα πληροφόρησης (π.χ. όταν όλα τα φορτία είναι άγνωστα ή όταν κάθε παίκτης γνωρίζει το μέγεθος του δικού του φορτίου) και αναλύσαμε για το καθένα το σύνολο και τις ιδιότητες των ισορροπιών Nash. Yπολογίσαμε επίσης φράγματα στο λόγο απόκλισης, ο οποίος εκφράζει την επίδραση που έχει στην απόδοση του συστήματος η εγωιστική συμπεριφορά των χρηστών του. Εκτός από τα υπολογιστικά θέματα που σχετίζονται με τη θεωρία παιγνίων, έχει ενδιαφέρον να μελετηθεί κατά πόσο μπορεί η θεωρία παιγνίων να βοηθήσει στην ανάπτυξη και ανάλυση αλγορίθμων για υπολογιστικά δύσκολα προβλήματα συνδυαστικής βελτιστοποίησης. Προς αυτήν την κατεύθυνση, μελετήσαμε από παιγνιοθεωρητική σκοπιά το πρόβλημα χρωματισμού των κορυφών ενός γραφήματος. Ορίσαμε κατάλληλα το παίγνιο χρωματισμού γραφήματος και αποδείξαμε ότι κάθε παίγνιο χρωματισμού γραφήματος έχει πάντα μια αγνή ισορροπία Nash, και ότι κάθε αγνή ισορροπία Nash αντιστοιχεί σε ορθό χρωματισμό του γραφήματος. Δείξαμε επίσης ότι υπάρχει πάντα μια αγνή ισορροπία Nash που χρησιμοποιεί βέλτιστο αριθμό χρωμάτων, δηλαδή ίσο με το χρωματικό αριθμό του γραφήματος. Επιπλέον, περιγράψαμε και αναλύσαμε έναν πολυωνυμικό αλγόριθμο που υπολογίζει μια αγνή ισορροπία Nash για ένα οποιοδήποτε παίγνιο χρωματισμού γραφήματος και χρησιμοποιεί συνολικά ένα πλήθος χρωμάτων που ικανοποιεί ταυτόχρονα τα περισσότερα κλασικά γνωστά φράγματα στο χρωματικό αριθμό. / We developed two algorithms for computing an e-approximate Nash equilibrium for the case where e is an absolute constant. The approximations achieved by our algorithms are e=3/4 and e=(2+l)/4 respectively, where $\lambda$ is the minimum, among all Nash equilibria, payoff of either player. Furthermore, we studied a wide class of random two player games, for which we showed how to compute an e-approximate Nash equilibrium, where e tends to zero as the number of strategies of the players tends to infinity. Game theoretic concepts are useful in determining the impact that selfish behavior plays on the global performance of a system involving selfish entities. Towards this direction, we focused on the problem of load balancing. We studied the case where the agents are not necessarily fully informed about the exact values of their loads. We focused on several models of information (e.g. when all agents know nothing about the loads, or when each agents knows her own load) and, for each model, we characterized the set of Nash equilibria and analyzed their properties. Moreover, we bounded the coordination ratio, a measure which captures the impact that selfish behavior has to the global performance of the system, in contrast to the performance achieved by an optimum centralized algorithm. Besides the computational issues related to game theory, it is interesting to investigate whether game theory can help us in developing and analyzing algorithms for computationally difficult combinatorial optimization problems. Towards this direction, we studied from a game theoretic point of view the problem of vertex coloring. In particular, we properly defined the graph coloring game and we proved that every graph coloring game has a pure Nash equilibrium, and each pure Nash equilibrium corresponds to a proper coloring of the graph. We also showed that there exists a pure Nash equilibrium that uses an optimum number of colors, i.e. equal to the chromatic number. Furthermore, we developed and analyzed a polynomial time algorithm that computes a pure Nash equilibrium for any graph coloring game, using a number of colors satisfying most of the known classical bounds on the chromatic number.

A coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices are given the same color. The chromatic number of a graph is the least number of colors needed to color all of its vertices. Graph coloring problems can be applied to many real world applications, such as scheduling and register allocation. Computationally, the decision problem of whether a general graph is m-colorable is NP-complete for m ≥ 3. The graph studied in this thesis is a well-known combinatorial object, the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for all k; however, coloring the square of the cube is a much more interesting problem. This is the graph in which the vertices are binary vectors of length k, and two vertices are adjacent if and only if the Hamming distance between the two vectors is at most 2. Any color class in a coloring of Q2k is a binary (k;M, 3) code. This thesis will begin with an introduction to binary codes and their structure. One of the most fundamental combinatorial problems is finding optimal binary codes, that is, binary codes with the maximum cardinality satisfying a specified length and minimum distance. Many upper and lower bounds have been produced, and we will analyze and apply several of these. This leads to many interesting results about the chromatic number of the square of the cube. The smallest k for which the chromatic number of Q2k is unknown is k = 8; however, it can be determined that this value is either 13 or 14. Computational approaches to determine the chromatic number of Q28 were performed. We were unable to determine whether 13 or 14 is the true value; however, much valuable insight was learned about the structure of this graph and the computational difficulty that lies within. Since a 13-coloring of Q28 must have between 9 and 12 color classes being (8; 20; 3) binary codes, this led to a thorough investigation of the structure of such binary codes.

In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.

Thesis (MScAgric)--University of Stellenbosch, 2004. / ENGLISH ABSTRACT: Rind colour is one of the most important external quality characteristics of citrus fruit and plays an important role in purchasing decisions by consumers. Consumers perceive brightlycoloured fruit to be sweet and mature, whereas citrus with a green rind is perceived to be sour and immature. However, there is a poor correlation between rind colour and internal quality, contradicting what is generally assumed by the fruit-buying public. In general, a bright orange rind colour improves consumer acceptance. Thus, it is important to ensure that the rind of citrus fruit is well-coloured on arrival at the market. Various pre-harvest cultural practices and postharvest techniques can be applied to improve rind colour. Degreening with ethylene gas is the most commonly used postharvest technology to improve rind colour, but has various negative side-effects. Degreened fruit are more prone to decay, have rinds which appear dull and flaccid, have been reported to develop off-flavours and have a shorter shelf-life period. Therefore, it is necessary to find alternatives to ethylene degreening and to extend shelf-life of citrus fruit. Under normal orchard conditions, rind colour development is associated with low night temperatures, usually experienced during autumn or following the passing of a cold front. To simulate cold front conditions, a hydrocooler and cold room were used to rapidly drop fruit temperature to 4 ºC for 6 hours, and then fruit were incubated at 20 to 22 ºC for 72 hours. This “cold shock” treatment of ‘Nules Clementine’ mandarin improved rind colour to a level similar to that of degreened fruit in the 2002 season due to a decrease in chlorophyll content and increase in carotenoid content. However, this result could not be repeated. Storage temperature is one of the most important postharvest factors affecting rind colour. Citrus fruit shipped to export markets requiring low temperatures (-0.6 ºC) for pest disinfestations purposes have been reported to arrive with poor rind colour. Shipping under low temperatures results in poor rind colour of fruit on arrival in the market. To comply with the USA’s phytosanitary requirement for imported citrus, fruit is held at -0.6 ºC for a minimum of 22 days. The effect of shipping at various temperatures (-0.6 ºC or 4.5 ºC), durations and the influence of initial rind colour, “orange” or “yellow”, on fruit colour upon arrival in the market was evaluated. Fruit shipped at a higher temperature (4.5 ºC) had a marginally better rind colour than fruit shipped at -0.6 ºC. The perceived loss of rind colour following shipping at sub-zero temperatures is probably due to carotenoid degradation. Therefore, initial rind colour plays a critical role in final product quality. Depending on market destination and shipping temperature, pale-coloured fruit should not be packed for markets sensitive to rind colour. Holding temperature after shipping can be effectively used to improve the rind colour of fruit arriving in the market with undesirable rind colour. An intermediate holding temperature of between 11 and 15 ºC resulted in the greatest improvement in rind colour after 2 weeks. A high holding temperature (20 ºC) caused colour degradation, whereas a low holding temperature (4.5 ºC) resulted in the maintenance of rind colour. By selecting the correct holding temperature, even after shipping at sub-zero temperatures, final colour can be improved. / AFRIKAANSE OPSOMMING: Tyd-temperatuur interaksie op na-oes skilkleur ontwikkeling by sitrus Skilkleur is een van die belangrikste eksterne kwaliteitseienskappe van die sitrusvrug en spëel ʼn belangrikke rol in wat verbruikers koop. Verbruikers verwag dat heldergekleurde vrugte soet en ryp sal wees, terwyl sitrus met ʼn groen skil geassosieer word met onrypheid en ʼn suur smaak. In teenstelling hiermee is daar egter ʼn swak korrelasie tussen skilkleur en interne kwaliteit. Aangesien ʼn heldergekleurde oranje skil verbruikersaanvaarding verbeter, is dit dus belangrik om te verseker dat die sitrusvrug ʼn goeie skilkleur het teen die tyd wat dit die mark bereik. Verskeie voor-oes bestuurspraktyke en na-oes tegnieke kan toegepas word om die skilkleur te verbeter. Ontgroening met etileen gas is die tegnologie wat mees algemeen gebruik word om skilkleur na oes te verbeter, maar dit het egter verskeie newe effekte tot gevolg. Ontgroende vrugte is meer vatbaar vir bederf en verwelkde skille met ʼn dowwe voorkoms. Afsmaake kan voorkom en ʼn verkorte rakleeftyd is al gerapporteer. Dit is dus noodsaaklik om ʼn alternatief vir etileen ontgroening te ontwikkel en die rakleeftyd van sitrusvrugte te verleng. Onder normale boordomstandighede word skilkleur ontwikkeling geassosieer met lae nag temperature wat gewoonlik in die herfs of na ʼn kouefront ondervind word. Om soortgelyke omstandighede na te boots, was ʼn “hydrocooler” en koelkamers gebruik om die temperatuur vinnig te laat daal tot by 4 °C en dit vir 6 uur daar te hou. Die vrugte was dan by 20 tot 22 °C geinkubeer vir 72 uur. Hierdie “koueskok” behandeling van ‘Nules Clementine’ mandaryn het skilkleur verbeter tot ʼn vlak vergelykbaar met ontgroende vrugte in die 2002 seisoen wat ontstaan het weens ʼn verlaging in chlorofil en ʼn toename in die karotinoïed inhoud van die skil. Opbergingstemperatuur is een van die belangrikste na-oes faktore wat skilkleur beinvloed. Sitrusvrugte wat verskeep word na uitvoermarkte wat lae temperature (-0.6 °C) vir disinfestasie vereis arriveer soms by die mark met ʼn swak skilkleur. Om die fitosanitêre vereistes vir die invoer van sitrus deur die VSA na tekom, was vrugte vir ʼn minimum van 22 dae by -0.6 °C gehou. Die effek van verskeping by verskeie temperature (-0.6 °C of 4.5 °C), tydperke en die invloed van aanvanklike skilkleur, “oranje” of “geel” was geevalueer by aankoms in die mark. Vrugte wat by hoër temperature (4.5 °C) verskeep was het ʼn effens beter skilkleur as vrugte by -0.6 °C getoon. Die verlies in skilkleur wat waargeneem word na verskeping onder vriespunt kan moontlik toegeskryf word aan karotenoiëd afbraak. Daarom speel aanvanklike skilkleur ʼn kritieke rol in finale produk kwaliteit. Die finale mark bestemming en verskepingstemperatuur sal bepaal of swakgekleurde vrugte verpak kan word. Opbergingstemperatuur na verskeping kan effektief gebruik word om die skilkleur van vrugte wat swak gekleur was met aankoms by die mark te verbeter. Matige temperature tussen 11 en 15 °C het na 2 weke die beste verbetering in skilkleur gelewer. Hoër temperature (20 °C) het skilkleur nadelig beinvloed, terwyl lae temperature skilkleur behou het. Deur die korrekte temperatuur te kies, selfs na verskeping by temperature onder vriespunt, kan uiteindelike skilkleur steeds verbeter word.