The queens graph Qn has the squares of then x n chessboard as its vertices; two squares are adjacent if they are in the same row, column or diagonal. A set D of squares of Qn is a dominating set for Qn if every square of Qn is either in D or adjacent to a square in D. If no two squares of a set I are adjacent then I is an independent set. Let 'J'(Qn) denote the minimum size of a dominating set of Qn and let i(Qn) denote the minimum size of an independent dominating set of Qn. The main purpose of this thesis is to determine new values for'!'( Qn). We begin by discussing the most important known lower bounds for 'J'(Qn) in Chapter 2. In Chapter 3 we state the hitherto known values of 'J'(Qn) and explain how they were determined. We briefly explain how to obtain all non-isomorphic minimum dominating sets for Q8 (listed in Appendix A). It is often useful to study these small dominating sets to look for patterns and possible generalisations. In Chapter 4 we determine new values for')' ( Q69 ) , ')' ( Q77 ), ')' ( Q30 ) and i (Q45 ) by considering asymmetric and symmetric dominating sets for the case n = 4k + 1 and in Chapter 5 we search for dominating sets for the case n = 4k + 3, thus determining the values of 'I' ( Q19) and 'I' (Q31 ). In Chapter 6 we prove the upper bound')' (Qn) :s; 1 8 5n + 0 (1), which is better than known bounds in the literature and in Chapter 7 we consider dominating sets on hexagonal boards. Finally, in Chapter 8 we determine the irredundance number for the hexagonal boards H5 and H7, as well as for Q5 and Q6 / Mathematical Sciences / D.Phil. (Applied Mathematics)

Graph augmentation concerns the addition of edges to a graph to satisfy some connectivity property of a graph. Previous research in this field has been preoccupied with edge augmentation; however the research in this document focuses on the addition of vertices to a graph to satisfy a specific connectivity property: ensuring that all the nodes of the graph are contained within cycles. A distinction is made between graph augmentation (edge addition), and graph enlargement (vertex addition). This document expands on previous research into a graph matching problem known as the “shoe matching problem” and the role of a graph enlargement algorithm in finding this solution. The aim of this research was to develop new and efficient algorithms to solve the graph enlargement problem as applied to the shoe matching problem and to improve on the naïve algorithm of Sanders. Three new algorithms focusing on graph enlargement and the shoe matching problem are presented, with positive results overall. The new enlargement algorithms: cost-optimised, matrix, and subgraph, succeeded in deriving the best result (least number of total nodes required) in 37%, 53%, and 57% of cases respectively (measured across 120 cases). In contrast, Sanders’s algorithm has a success rate of only 20%; thus the new algorithms have a varying success rate of approximately 2 to 3 times that of Sanders’s algorithm. / Computing / M. Sc. Computing

La problèmatique dont nous nous occupons dans cette thèse est la classification automatique d'images bidimensionnelles, ainsi que la détection d'objets génériques dans des images. Les avancées de ce champ de recherche contribuent à l'élaboration de systèmes intelligents, tels que des robots autonomes et la création d'un web sémantique. Dans ce contexte, la conception de représentations d'images et de classificateurs appropriés constituent des problèmes ambitieux. Notre travail de recherche fournit des solutions à ces deux problèmes, que sont la représentation et la classification d'images. Afin de générer notre représentation d'image, nous extrayons des attributs visuels de l'image et construisons une structure de graphe basée sur les propriétés liées au relations de proximités entre les points d'intérêt associés. Nous montrons que certaines propriétés spectrales de ces graphes constituent de bons invariants aux classes de transformations géométriques rigides. Notre représentation d'image est basée sur ces propriétés. Les résultats expérimentaux démontrent que cette représentation constitue une amélioration par rapport à d'autres représentations similaires, mais qui n'intègrent pas les informations liées à l'organisation spatiale des points d'intérêt. Cependant, un inconvénient de cette méthode est qu'elle fait appel à une quantification (avec pertes) de l'espace des attributs visuels afin d'être combinée avec un classificateur Support Vecteur Machine (SVM) efficace. Nous résolvons ce problème en créant un nouveau classificateur, basé sur la distance au plus proche voisin, et qui permet la classification d'objets assimilés à des ensembles de points. La linéarité de ce classificateur nous permet également de faire de la détection d'objet, en plus de la classification d'images. Une autre propriété intéressante de ce classificateur est sa capacité à combiner différents types d'attributs visuels de manière optimale. Nous utilisons cette propriété pour formuler le problème de classification de graphes de manière différente. Les expériences, menées sur une grande variété de jeux de données, montrent les bénéfices quantitatifs de notre approche. / We are concerned in this thesis by the problem of automated 2D image classification and general object detection. Advances in this field of research contribute to the elaboration of intelligent systems such as, but not limited to, autonomous robots and the semantic web. In this context, designing adequate image representations and classifiers for these representations constitute challenging issues. Our work provides innovative solutions to both these problems: image representation and classification. In order to generate our image representation, we extract visual features from the image and build a graphical structure based on properties of spatial proximity between the feature points. We show that certain spectral properties of this graph constitute good invariants to rigid geometric transforms. Our representation is based on these invariant properties. Experiments show that this representation constitutes an improvement over other similar representations that do not integrate the spatial layout of visual features. However, a drawback of this method is that it requires a lossy quantisation of the visual feature space in order to be combined with a state-of-the-art support vector machine (SVM) classifier. We address this issue by designing a new classifier. This generic classifier relies on a nearest-neighbour distance to classify objects that can be assimilated to feature sets, i.e: point clouds. The linearity of this classifier allows us to perform object detection, in addition to image classification. Another interesting property is its ability to combine different types of visual features in an optimal manner. We take advantage of this property to produce a new formulation for the classification of visual feature graphs. Experiments are conducted on a wide variety of publicly available datasets to justify the benefits of our approach.

abstract: The Kuramoto model is an archetypal model for studying synchronization in groups of nonidentical oscillators where oscillators are imbued with their own frequency and coupled with other oscillators though a network of interactions. As the coupling strength increases, there is a bifurcation to complete synchronization where all oscillators move with the same frequency and show a collective rhythm. Kuramoto-like dynamics are considered a relevant model for instabilities of the AC-power grid which operates in synchrony under standard conditions but exhibits, in a state of failure, segmentation of the grid into desynchronized clusters. In this dissertation the minimum coupling strength required to ensure total frequency synchronization in a Kuramoto system, called the critical coupling, is investigated. For coupling strength below the critical coupling, clusters of oscillators form where oscillators within a cluster are on average oscillating with the same long-term frequency. A unified order parameter based approach is developed to create approximations of the critical coupling. Some of the new approximations provide strict lower bounds for the critical coupling. In addition, these approximations allow for predictions of the partially synchronized clusters that emerge in the bifurcation from the synchronized state. Merging the order parameter approach with graph theoretical concepts leads to a characterization of this bifurcation as a weighted graph partitioning problem on an arbitrary networks which then leads to an optimization problem that can efficiently estimate the partially synchronized clusters. Numerical experiments on random Kuramoto systems show the high accuracy of these methods. An interpretation of the methods in the context of power systems is provided. / Dissertation/Thesis / Doctoral Dissertation Applied Mathematics 2018

Un fasciagraphe de taille n et de fibre F est constitué de n copies consécutives du graphe F, chaque copie étant reliée à la suivante selon le même schéma. Les rotagraphes sont définis similairement, mais selon une structure circulaire. Dans cette thèse nous caractérisons un ensemble de problèmes combinatoires qui peuvent être résolus de façon efficace dans la classe des fasciagraphes et rotagraphes. Dans ce contexte, nous définissons les (d,q,w)-propriétés closes et stables, et présentons pour de telles propriétés un algorithme pour calculer une solution optimale en temps constant pour l'ensemble des fasciagraphes ou rotagraphes de fibre fixée. Nous montrons que plusieurs problèmes communément étudiés dans la théorie des graphes et NP-complets dans le cas général sont caractérisés par des (d,q,w)-propriétés closes ou stables. Dans une seconde partie de la thèse, nous adaptons cet algorithme générique à trois problèmes spécifiques caractérisés par des (d,q,w)-propriétés stables : le problème du code identifiant minimum, et deux problèmes proches, celui de dominant-localisateur minimum et celui du dominant-total-localisateur minimum. Nous présentons alors une implémentation de l'algorithme qui nous a permis de répondre à des questions ouvertes dans certains rotagraphes particuliers : les bandes circulaires de hauteur bornée. Nous en déduisons d'autres résultats sur les bandes infinies de hauteur bornée. Enfin, nous explorons le problème du code identifiant dans une autre classe de graphes à structure répétitive : les graphes fractals de cycle. / A fasciagraph of length n and of fiber F, is constituted of n consecutive copies of a graph F, each copy being linked to the next one according to a same scheme. Rotagraphs are defines similarily, but along a circular structure. In this thesis, we caracterize a set of combinatorial problems that can be efficiently solved when applied on the class of rotagraphs and fasciagraphs. In this context, we define closed and stable (d,q,w)-properties, and we present, for such properties, an algorithm to compute an optimal solution, in constant time, for the set of fasciagraphs or rotagraphs of fixed fiber. We show that several problems, largely studied in graph theory, are caracterized by closed or stable (d,q,w)-properties. In a second part of the thesis, we adapt the generic algorithm to three problems caracterized by stable (d,q,w)-properties : the problem of minimum indentifying code, and two other, close to this one, the problem of minimum locating-dominating set et the one of minimum locating-total-dominating set. We present an implementation of our algorithm which has let us respond to open questions in a certain sub-class of rotagraphs : the circular strips of bounded height. We deduce from there other results on infinite strips of bounded height. Finaly we explore the problem of minimum identifying code in another class of graphs with repetitive structure : the fractal graphs.

O problema de geração de estruturas de coalizão (CSG) envolve o particionamento do conjunto de agentes em todos os subconjuntos(ou, coalizões) possíveis. O que torna esse problema desafiador é o número de coalizões possíveis crescer exponencialmente a medida que novos agentes são inseridos, o número de coalizões é (2n − 1) onde n é o número de agentes. Entretanto, em muitas aplicações do mundo real, existem limitações inerentes nas coalizões possíveis: por exemplo, determinados agentes podem ser proibidos de estar na mesma coalizão, ou a estrutura de coalizão pode ser obrigada a conter coalizões do mesmo tamanho. Quando consideramos CSG restrito por grafos, onde a viabilidade de uma coalizão é restrita por um grafo de sinergia dos agentes, a complexidade computacional pode ser a mesma ou menor, dependendo do que se considera uma coalizão válida. Os grafos de sinergia são representações dos agentes como sendo os vértices e as suas relações são as arestas. Este trabalho é um estudo sobre a utilização de restrições envolvendo grafos como uma heurística sobre as coalizões para o problema enumeração de coalizão, de forma a considerar uma coalizão factível ou não de acordo com a densidade do subgrafo induzido pelos agentes. Os trabalhos atuais, que utilizam os grafos de restrição como heurística para reduzir a complexidade computacional, consideram uma coalizão válida somente se o subgrafo formado pelos agentes da coalizão é conexo. Verificou-se experimentalmente para grafos com a propriedade power law, comum em uma variedade de grafos reais, que restringir uma coalizão válida como sendo um subgrafo conexo pode não ser uma redução significativa. Entretanto a utilização de um subgrafo com restrições mais fortes, em particular uma clique garante uma redução exponencial do número de coalizões consideradas. Não existem teoremas que possam calcular qual a quantidade de subgrafos conexos ou mesmo o número de cliques em um grafo do tipo power law. No presente trabalho foi possível calcular experimentalmente para grafos power law com ate 17 vértices, sendo que também são apresentados resultados analíticos para grafos estrela (Kn−1,1 ). Os grafos estrela são uma aproximação aceitável, pois formam um hub, estrutura característica de grafos power law. Como trabalhos futuros podem ser citados: o mapeamento de domínios para os quais a restrição de clique seria adequada, além do desenvolvimento de um algoritmo que incorpore a restrição diretamente na contagem de coalizões validas. / The coalition structures generating problem (CSG) involves partitioning the set of agents in all possible subsets (or coalitions). What makes this problem challenging is the number of possible coalitions that grows exponentially as new agents are inserted. The number of coalitions is (2n − 1) where n is the number of agents. However, in many real-world applications, there are inherent limitations on possible coalitions: for example, some individuals may be prohibited from being in the same coalition or coalition structure may be required to contain coalitions of the same size. When we consider CSG restricted by graphs where the viability of a coalition is restricted by a synergy graph, the computational complexity can be maintained or eventually be smaller depending on what is considered a valid coalition. Synergy graphs are representations of the agents as being the vertices and their relationships are the edges. This work is a study on the use of restrictions involving graphs as a heuristic about coalitions for the problem coalition enumeration in order to consider a feasible coalition or not according to the density of the subgraph induced by the agents. Current works using the restriction graphs as heuristics to reduce the computational complexity, consider a coalition valid only if the subgraph formed by the agents of the coalition is connected. In this work it as experimentally verify for power law graphs, present in a variety of real graphs, that restricting availability coalition as a connected subgraph may in not prohibited a significant gain. However, they using a subgraphs with strong restrictions, in particular a clique, guarantees an exponential reduction in the number of considered coalition. There no are theorems calculate subgraphs or even the number of cliques on a type power law graph. In the present work it was possible to calculate values experimental for graphs of up to 17 vértices, being also presented analytics results for star graphs (Kn−1,1 ). Star graphs are an acceptable approximation, was they account for hubs, a characteristic structure of power law graphs. As future works can be cited the study of domains where the clique restriction is adequate as well as the development of an algorithm that incorporates the restriction for coalition counting.

A identificação de formas apresenta inúmeras aplicações na área de visão computacional, pois representa uma poderosa ferramenta para analisar as características de um objeto. Dentre as aplicações, podemos citar como exemplos a interação entre humanos e robôs, com a identificação de ações e comandos, e a análise de comportamento para vigilância com a biometria não invasiva. Em nosso trabalho nós desenvolvemos um novo descritor de formas 2D baseado na utilização de redes complexas e teoria espectral de grafos. O contorno da forma de um objeto é representado por uma rede complexa, onde cada ponto pertencente a forma será representado por um vértice da rede. Utilizando uma dinâmica gerada artificialmente na rede complexa, podemos definir uma série de matrizes de adjacência que refletem a dinâmica estrutural da forma do objeto. Cada matriz tem seu espectro calculado, e os principais autovalores são utilizados na construção de um vetor de características. Esse vetor, após aplicar as operações de módulo e normalização, torna-se nossa assinatura espectral de forma. Os principais autovalores de um grafo estão relacionados com propriedades topológicas do mesmo, o que permite sua utilização na descrição da forma de um objeto. Para validar nosso método, nós realizamos testes quanto ao seu comportamento frente a transformações de rotação e escala e estudamos seu comportamento quanto à contaminação das formas por ruído Gaussiano e quanto ao efeito de oclusões parciais. Utilizamos diversas bases de dados comumente utilizadas na literatura de análise de formas para averiguar a eficiência de nosso método em tarefas de recuperação de informação. Concluímos o trabalho com a análise qualitativa do comportamento de nosso método frente a diferentes curvas e estudando uma aplicação na análise de sequências de caminhada. Os resultados obtidos em comparação aos outros métodos mostram que nossa assinatura espectral de forma apresenta bom resultados na precisão de recuperação de informação, boa tolerância a contaminação das formas por ruído e oclusões parciais, e capacidade de distinguir ações humanas e identificar os ciclos de uma sequência de caminhada. / The shape is a powerful feature to characterize an object and the shape analysis has several applications in computer vision area. We can cite the interaction between human and robots, surveillance, non-invasive biometry and human actions identifications among other applications. In our work we have developed a new 2d shape descriptor based on complex network and spectral graph theory. The contour shape of an object is represented by a complex network, where each point belonging shape is represented by a vertex of the network. A set of adjacencies matrices is generated using an artificial dynamics in the complex network. We calculate the spectrum of each adjacency matrix and the most important eigenvalues are used in a feature vector. This vector, after applying module and normalization operations, becomes our spectral shape signature. The principal eigenvalues of a graph are related to its topological properties. This allows us use eigenvalues to describe the shape of an object. We have used shape benchmarks to measure the information retrieve precision of our method. Besides that, we have analyzed the response of the spectral shape signature under noise, rotation and occlusions situations. A qualitative study of the method behavior has been done using curves and a walk sequence. The achieved comparative results to other methods found in the literature show that our spectral shape signature presents good results in information retrieval tasks, good tolerance under noise and partial occlusions situation. We present that our method is able to distinguish human actions and identify the cycles of a walk sequence.

abstract: The cyber-physical systems (CPS) are emerging as the underpinning technology for major industries in the 21-th century. This dissertation is focused on two fundamental issues in cyber-physical systems: network interdependence and information dynamics. It consists of the following two main thrusts. The first thrust is targeted at understanding the impact of network interdependence. It is shown that a cyber-physical system built upon multiple interdependent networks are more vulnerable to attacks since node failures in one network may result in failures in the other network, causing a cascade of failures that would potentially lead to the collapse of the entire infrastructure. There is thus a need to develop a new network science for modeling and quantifying cascading failures in multiple interdependent networks, and to develop network management algorithms that improve network robustness and ensure overall network reliability against cascading failures. To enhance the system robustness, a "regular" allocation strategy is proposed that yields better resistance against cascading failures compared to all possible existing strategies. Furthermore, in view of the load redistribution feature in many physical infrastructure networks, e.g., power grids, a CPS model is developed where the threshold model and the giant connected component model are used to capture the node failures in the physical infrastructure network and the cyber network, respectively. The second thrust is centered around the information dynamics in the CPS. One speculation is that the interconnections over multiple networks can facilitate information diffusion since information propagation in one network can trigger further spread in the other network. With this insight, a theoretical framework is developed to analyze information epidemic across multiple interconnecting networks. It is shown that the conjoining among networks can dramatically speed up message diffusion. Along a different avenue, many cyber-physical systems rely on wireless networks which offer platforms for information exchanges. To optimize the QoS of wireless networks, there is a need to develop a high-throughput and low-complexity scheduling algorithm to control link dynamics. To that end, distributed link scheduling algorithms are explored for multi-hop MIMO networks and two CSMA algorithms under the continuous-time model and the discrete-time model are devised, respectively. / Dissertation/Thesis / Ph.D. Electrical Engineering 2012

MinistÃre de l'Enseignement SupÃrieur et de la Recherche / Nesta tese, estudamos vÃrios problemas de teoria dos grafos relativos à coloraÃÃo e convexidade em grafos. A maioria dos resultados contidos aqui sÃo ligados à complexidade computacional destes problemas para classes de grafos particulares. Na primeira, e principal, parte desta tese, discutimos coloraÃÃo de grafos que à uma das Ãreas mais importantes de teoria dos grafos. Primeiro, consideramos trÃs problemas de coloraÃÃo chamados coloraÃÃo gulosa, coloraÃÃo ponderada e coloraÃÃo ponderada imprÃpria. Em seguida, discutimos um problema de decisÃo, chamado boa rotulagem de arestas, cuja definiÃÃo foi motivada pelo problema de atribuiÃÃo de frequÃncias em redes Ãticas. A segunda parte desta tese à dedicada a um parÃmetro de otimizaÃÃo em grafos chamado de nÃmero de fecho (geodÃtico). A definiÃÃo deste parÃmetro à motivada pela extensÃo das noÃÃes de conjuntos e fecho convexos no espaÃo Euclidiano. Por m, apresentamos em anexo outros trabalhos desenvolvidos durante esta tese, um em hipergrafos dirigidos Eulerianos e Hamiltonianos e outro sobre sistemas de armazenamento distribuÃdo. / In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose definition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The definition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems.

Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.