Every graph G contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set (equivalently, a dominating set) in G. Among all such minimum vertex-colorings of the vertices of G, a coloring with the maximum number of color classes that are dominating sets in G is called a dominating-χ-coloring of G. The number of color classes that are dominating sets in a dominating-χ-coloring of G is defined to be the dominating-χ-color number of G. In this paper, we continue to investigate the dominating-χ-color number of a graph first defined and studied in [1].

We consider a variety of types of vertex sequences, which are defined in terms of a requirement that the next vertex in the sequence must meet. For example, let S = (v1, v2, …, vk ) be a sequence of distinct vertices in a graph G such that every vertex vi in S dominates at least one vertex in V that is not dominated by any of the vertices preceding it in the sequence S. Such a sequence of maximal length is called a dominating sequence since the set {v1, v2, …, vk } must be a dominating set of G. In this paper we survey the literature on dominating and other related sequences, and propose for future study several new types of vertex sequences, which suggest the beginning of a theory of vertex sequences in graphs.

This work describes the design and implementation of a generic architecture to provide a collective solution for power-aware routing to a wide range of problems in wireless sensor network environments. Power aware-routing is integral to the proposed solutions for different problems. These solutions try to achieve power-efficient routing specific to the problem domain. This can lead to challenging technical problems and deployment barriers when attempting to integrate the solutions. This work extracts various factors to be considered for a range of problems in wireless sensor networks and provides a generic framework for efficient power-aware routing. The architecture aims to relieve researchers from considering power management in their design. We have identified coupling between sources and sinks as the main factor for different design choices for a range of problems. We developed a core-based hierarchical routing framework for efficient power-aware routing that is used to decouple the sources from sinks. The architecture uses only local interaction for scalability and stability in a dynamic network. The architecture provides core-based query forwarding and data dissemination. It uses data aggregation and query aggregation at core nodes to reduce the amount of data to be transmitted. The architecture can be easily extended to incorporate protocols to provide QoS and security to the applications. We use network simulations to evaluate the performance of cluster formation and energy efficiency of the algorithm. Our results show that energy efficiency of the algorithm is better when the transmission range is kept to a minimum for network connectivity as compared to adjustable transmission range.

[pt] Esta tese faz um estudo do problema do Conjunto Dominante, um problema NP-difícil de grande relevância em aplicações relacionadas ao projeto de rede sem fio, mineração de dados, teoria de códigos, dentre outras. O conjunto dominante mínimo em um grafo é um conjunto mínimo de vértices de modo que cada vértice do grafo pertence a este conjunto ou é adjacente a um vértice que pertence a ele. Três variantes do problema foram estudadas; primeiro, uma variante na qual considera pesos nos vértices, buscando um conjunto dominante com menor peso total; segundo, uma variante onde o subgrafo induzido pelo conjunto dominante está conectado; e, finalmente, a variante que engloba essas duas características. Para resolver esses três problemas, propõe-se um algoritmo híbrido baseado na meta-heurística busca tabu com componentes adicionais de programação matemática, resultando em um método por vezes chamado de mateurística, (matheuristic, em inglês). Diversas técnicas adicionais e vizinhanças largas foram propostas afim de alcançar regiões promissoras no espaço de busca. Análises experimentais demonstram a contribuição individual de todos esses componentes. Finalmente, o algoritmo é testado no problema do código de cobertura mínima, que pode ser visto como um caso especial do problema do conjunto dominante. Os códigos são estudados na métrica Hamming e na métrica Rosenbloom-Tsfasman. Neste último, diversos códigos menores foram encontrados. / [en] This thesis addresses the Dominating Set Problem, an NP- hard problem with great relevance in applications related to wireless network design, data mining, coding theory, among others. The minimum dominating set in a graph is a minimal set of vertices so that each vertex of the graph belongs to it or is adjacent to a vertex of this set. We study three variants of the problem: first, in the presence of weights on vertices, searching for a dominating set with smallest total weight; second, a variant where the subgraph induced by the dominating set needs to be connected, and,finally, the variant that encompasses these two characteristics. To solve these three problems, we propose a hybrid algorithm based on tabu search with additional mathematical-programming components, leading to a method sometimes called matheuristic. Several additional techniques and large neighborhoods are also employed to reach promising regions in the search space. Our experimental analyses show the good contribution of all these individual components. Finally, the algorithm is tested on the covering code problem, which can be viewed as a special case of the minimum dominating set problem. The codes are studied for the Hamming metric and the Rosenbloom-Tsfasman metric. For this last case, several shorter codes were found.

De nombreux problèmes algorithmiques sont « difficiles », dans le sens où on ne sait pas les résoudre en temps polynomial par rapport à la taille de l’entrée, soit parce qu’ils sont NP-difficiles, soit, pour certains problèmes d’énumération, à cause du nombre exponentiel d'objets à énumérer. Depuis une quinzaine d’années on trouve un intérêt grandissant dans la littérature pour la conception d'algorithmes exacts sophistiqués afin de les résoudre le plus efficacement possible. Dans le cadre de cette thèse, nous nous intéressons à la conception d'algorithmes exacts exponentiels autour de trois problèmes difficiles. Nous étudions tout d'abord le problème d'optimisation Ensemble Connexe Tropical pour lequel nous décrivons un algorithme afin de le résoudre en général, puis un algorithme de branchement plus rapide pour le résoudre sur les arbres, ce problème restant difficile même dans ce cas. Nous nous intéressons ensuite au problème d'énumération Ensembles Dominants Minimaux, pour lequel nous donnons des algorithmes résolvant ce problème dans les graphes splits, cobipartis, ainsi que dans les graphes d'intervalles. Nous déduisons des bornes supérieures sur le nombre d'ensembles dominants minimaux admis par de tels graphes. La dernière étude de cette thèse concerne le problème d'optimisation Domination Romaine Faible dans lequel, étant donné un graphe nous cherchons à construire une fonction de pondération selon certaines propriétés. Le problème est NP-difficile en général, mais nous donnons un algorithme glouton linéaire calculant une telle fonction pour les graphes d'intervalles. / Many algorithmic problems are « hard », in the sense of we do not know how to solve them in polynomialtime, either because they are NP-hard, or, for some enumeration problems, because the number of objectsto be produced is exponential. During the last fifteen years there was a growing interest in the design of exact algorithms to solve such problems as efficiently as possible. In the context of this thesis, we focus on the design of exponential exact algorithms for three hard problems. First, we study the optimisation problem Tropical Connected Set for which we describe an algorithm to solve it in the general case, then a faster branch-and-reduce algorithm to solve it on trees; the problem remains difficult even in this case. Secondly we focus on the Minimal Dominating Sets enumeration problem, for which we give algorithms to solve it on split, cobipartite and intervals graphs. As a byproduct, we establish upper bounds on the number of minimal dominating sets in such graphs. The last focus of this thesis concerns the Weak Roman Domination optimisation problem for which, given a graph, the goal is to build a weight function under some properties. The problem is NP-hard in general, but we give a linear greedy algorithm which computes such a function on interval graphs.

Dans cette thèse, nous étudions les aspects structurels et algorithmiques de différents problèmes de théorie des graphes. Rappelons qu’un graphe est un ensemble de sommets éventuellement reliés par des arêtes. Deux sommets sont adjacents s’ils sont reliés par une arête.<p>Tout d’abord, nous considérons les deux problèmes suivants :le problème de vertex cover et celui de dominating set, deux cas particuliers du problème de hitting set. Un vertex cover est un ensemble de sommets qui rencontrent toutes les arêtes alors qu’un dominating set est un ensemble X de sommets tel que chaque sommet n’appartenant pas à X est adjacent à un sommet de X. La version connexe de ces problèmes demande que les sommets choisis forment un sous-graphe connexe. Pour les deux problèmes précédents, nous examinons le prix de la connexité, défini comme étant le rapport entre la taille minimum d’un ensemble répondant à la version connexe du problème et celle d’un ensemble du problème originel. Nous prouvons la difficulté du calcul du prix de la connexité d’un graphe. Cependant, lorsqu’on exige que le prix de la connexité d’un graphe ainsi que de tous ses sous-graphes induits soit borné par une constante fixée, la situation change complètement. En effet, pour les problèmes de vertex cover et de dominating set, nous avons pu caractériser ces classes de graphes pour de petites constantes.<p>Ensuite, nous caractérisons en termes de dominating sets connexes les graphes Pk- free, graphes n’ayant pas de sous-graphes induits isomorphes à un chemin sur k sommets. Beaucoup de problèmes sur les graphes sont étudiés lorsqu’ils sont restreints à cette classe de graphes. De plus, nous appliquons cette caractérisation à la 2-coloration dans les hypergraphes. Pour certains hypergraphes, nous prouvons que ce problème peut être résolu en temps polynomial.<p>Finalement, nous travaillons sur le problème de Pk-hitting set. Un Pk-hitting set est un ensemble de sommets qui rencontrent tous les chemins sur k sommets. Nous développons un algorithme d’approximation avec un facteur de performance de 3. Notre algorithme, basé sur la méthode primal-dual, fournit un Pk-hitting set dont la taille est au plus 3 fois la taille minimum d’un Pk-hitting set. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

This master thesis discusses various mathematical problems related to the placement of chess pieces. Solutions to the problems are mostly elementary (yet sometimes quite inventive), in some cases rely on basic knowledge of graph theory. We successively focus on different chess pieces and their tours on rectangular boards, and then examine the "independence" and "domination" of chess pieces on square boards. The text is complemented with numerous pictures illustrating particular solutions to given problems.

Historians use different types of sources when reconstructing the past. of the two major categories of sources, the primary sources are of major importance for attaining information, as they are contemporary to the period which is being researched. They are often more reliable than the other category, namely secondary sources, which are literally second-hand information. However, all possible sources, both primary and secondary, must be approached critically so as to obtain a balanced version of the past. In the South African situation, for an extensive period of time, most of the historical writing on the early periods was based on the records which were made by the Europeanoriginated Whites who had the advantage of being able to put their accounts in writin~. This led to the European-White perspective dominating and monopolising the historiographical stage for quite a long time. The perspective of the indigenous inhabitants of South Africa had been overshadowed owing to their inability to read and write. The written sources on the Blacks in South Africa date back to the time when the first Europeans set foot here. The early European travellers (traders, hunters, natural scientists, etc.) came into contact with the Black communities and they made records on them. Obviously these travellers based such records on their own interests and also wrote from a Eurocentric position, with cultural differences as well as racial prejudices and superior attitudes towards the Blacks. The missionaries, who were mostly of European origin, also made records about the Blacks among whom they worked. The missionaries also had their own agenda, although different from that of the travellers. The records which they kept mostly reflected their "fight" against what they thought were barbaric and backward ways of the Blacks' lifestyle. In addition to the records made by the early travellers and missionaries about the Blacks, there were records which were made by the Boer and British government officials. In this study the official records pertaining to the Blacks in the Transvaal between 1902 and 1907 are discussed. Firstly, a historiographical overview is presented and secondly, the official records themselves are analysed and evaluated. The importance of those records as sources of information on the Blacks in the Transvaal, especially the Northern Sotho, is evaluated by using different criteria, including the Principle of internal criticism. There are numerous flaws and limitations found in these records about Blacks such as cultural differences, subjectivity, prejudice, bias, etc. However, even though these records contain such flaws, they are still important sources of information. Their most important value is that they form the basis and point of departure from where historical reconstruction is made. Research, even in future, would still heavily depend on these records as sources of information. But, as already pointed out, the information obtained in them has to be tested by different criteria in order to detect the limitations, so that a more balanced reconstructions can be achieved. / Dissertation (MA)--University of Pretoria, 2001. / gm2014 / Historical and Heritage Studies / Unrestricted

Dans ce travail, nous nous intéressons à une topologie pour les réseaux de capteurs sans fil. Un réseau de capteurs sans fil peut être modélisé comme un graphe non orienté G = (V,E). Chaque sommet de V représente un capteur et une arête e = {u, v} dans E indique une transmission directe possible entre deux capteurs u et v. Contrairement aux dispositifs filaires, les capteurs sans fil ne sont pas a priori agencé en réseau. Une topologie doit être créée en sélectionnant des noeuds "dominants" qui vont gérer les transmissions. Les architectures qui ont été examinées dans la littérature reposent essentiellement sur les ensembles dominants connexes et les ensembles dominants faiblement connexes. Cette étude est consacrée aux ensembles indépendants faiblement connexes. Un indépendant S ⊂ V est dit faiblement connexe si le graphe GS = (V, [S, V \S]) est connexe, où [S, V \S] est l’ensemble des arêtes e = {u, v} de E avec u ∈ S et v ∈ V \S. Une topologie basée sur les ensembles faiblement connexes permet de partitionner l’ensemble des capteurs en trois groupes, les esclaves, les maîtres et les intermédiaires. Les premiers effectuent les mesures, les seconds rassemblent les données collectées et les troisièmes assurent les communications inter-groupes. Nous donnons d’abord quelques propriétés de cette structure combinatoire lorsque le graphe non orienté G est connexe. Puis nous proposons des résultats de complexité pour le problème de la recherche de l’indépendant faiblement connexe de cardinalité minimale (MWCISP). Nous décrivons également un algorithme d’énumération exact de complexité O∗(1.4655|V |) pour le MWCISP. Des tests numériques de cette procédure exacte sont présentés. Nous formulons ensuite le MWCISP comme un programme linéaire en nombres entiers. Le polytope associé aux solutions de ce problème est complètement caractérisé lorsque G est un cycle impair. Nous étudions des opérations de composition de graphes et leurs conséquences polyédrales. Nous introduisons des inégalités valides notamment les contraintes dites de multibord. Par la suite, nous développons un algorithme de coupes et branchement sous CPLEX pour résoudre ce problème en utilisant des heuristiques pour la séparation de nos familles de contraintes. Des résultats expérimentaux de ce programme sont exposés. / In this work, we focus on a topology for Wireless Sensor Networks (WSN). A wireless sensor network can be modeled as an undirected graph G = (V,E). Each vertex of V represents a sensor and an edge e = {u, v} in E implies a direct transmission between the two sensors u and v. Unlike wired devices, wireless sensors are not a priori arranged in a network. Topology should be made by selecting some sensor as dominators nodes who manage transmissions. Architectures that have been studied in the literature are mainly based on connected dominating sets and weakly connected dominating sets.This study is devoted to weakly connected independent sets. An independent set S ⊂ V is said Weakly Connected if the graph GS = (V, [S, V \S]) is connected, where [S, V \S] is the set of edges with exactly one end in S. A sensor network topology based on weakly connected sets is partition into three groups, slaves, masters and bridges. The first performs the measurements, the second gathers the collected data and the later provides the inter-group communications. We first give some properties of this combinatorial structure when the undirected graph G is connected. Then we provide complexity results for the problem of finding the minimum weakly connected independent set problem (MWCISP). We also describe an exact enumeration algorithm of complexity O∗(1.4655|V |) (for the (MWCISP)). Numerical tests of this exact procedure are also presented. We then present an integer programming formulation for the minimum weakly connected independent set problem and discuss its associated polytope. Some classical graph operations are also used for defining new polyhedra from pieces. We give valid inequalities and describe heuristical separation algorithms for them. Finally, we develop a branch-and-cut algorithm and test it on two classes of graphs.

L'objet de cette thèse sur les réseaux de capteurs est l'étude du déploiement minimal de capteurs lorsque ceux-ci doivent couvrir un ensemble discret de cibles plutôt que des superficies. Après la présentation des caractéristiques d'un réseau de capteurs, et l'intérêt d'un déploiement minimal, nous en proposons une modélisation en théorie des graphes. Nous présentons ensuite un état de l'art décrivant certaines techniques de résolution par la programmation mathématique de diverses problématiques dans ce type de réseau. Nous utilisons plusieurs programmes linéaires en variables mixtes afin de résoudre le problème du déploiement minimal des capteurs sous des contraintes de couverture de toutes les cibles et de connectivité des capteurs entre eux. Finalement, nous concevons une nouvelle heuristique de calcul de placement de capteurs lorsque les cibles sont placées sur une grille à motif carré et nous conjecturons que cette heuristique retourne une solution optimale dans tous les cas. / The objectif of this thesis on wireless sensor networks is to study the deployment of a minimal number of sensors to cover specific targets instead of continuous areas. After a presentation of the characteristics of wireless sensor networks, and after justifying the interest of an optimal sensor deployment, we propose a graph-theory based model for wireless sensor networks. We then present a state of the art describing various mathematical programming models and resolution techniques regarding a number of optimization problems in such networks. We formulate several Mixed Integer Linear programs to solve the optimal sensor deployment problem under contraints related to the coverage of all targets and connectivity between sensors. Finally, we conceive a new heuristic for sensor placement when targets are placed in a square grid graph, and we conjecture that this heuristic returns an optimal solution in all cases.