[pt] As redes de sensores sem fio se constituem numa área que outorga grandes oportunidades para a oferta de uma série de aplicações inovadoras e com baixo custo. Os dispositivos destas redes são bastantes pequenos e sua fonte de alimentação são baterias. O tempo de vida destas é limitado, limitando assim o tempo da vida dos sensores e da rede como um todo. Por esta razão nos últimos anos o tema de eficiência energética tem atraído grande interesse de pesquisadores. O aumento do custo da energia e do consumo global da energia pelo setor de ICT (Information and Communications Technologies) têm crescido vertiginosamente devido ao aumento continuo do número de clientes e da demanda por aplicações de maior complexidade. Por tudo isso têm sido desenvolvidos distintos métodos e técnicas para economizar energia nas RSSF. Neste trabalho se implementam dois algoritmos que levam em conta critérios para economizar os custos de energia da rede e através de experimentos de simulação se avalia os mesmos. Nos resultados pode se observar as vantagens de trabalhar com sistemas que visam a eficiência energética. / [en] The WSNs (Wireless Sensor Networks) belong to an area that gives rise to great opportunities to spread innovative and low cost applications. These kinds of networks are composed of tiny devices with limited energy. The main source of power supply for WSNs are batteries, which are limited in cycle life, thus limiting the sensors lifetime and the network as a whole. Due to that fact, the energy efficiency network is becoming the main concern to be addressed by researchers. Rising energy prices and global energy consumption by the ICT (Information and Communications Technologies) sector have grown dramatically due to the continuous increase in customer number and the demand for more complex applications. For the reasons outlined above, different energy-saving techniques for WSNs have been developed. Two energy-saving algorithms for WSNs were implemented in this thesis, and they were tested by experimental evaluation using simulation. The results obtained from the simulations showed the advantages of working with systems aiming at energy efficiency.

Cette thèse s’intéresse à la question de l’évaluation des Systèmes Multi-Agents (SMA). Les caractéristiques propres que possèdent ces derniers, notamment en termes d’autonomie, de distribution, de dynamique et de socialité, ont grandement contribué à l’élargissement de leurs champs d’application, mais en contrepartie, elles ont rendu leur analyse plus ardue. Ainsi, les méthodes d’évaluation dans les systèmes informatiques classiques s’avèrent insuffisantes à analyser les SMA, étant donné qu’elles ne tiennent pas compte de leurs spécificités. L’objectif de cette thèse consiste donc à proposer une approche générique pour l’évaluation des SMA en se basant sur la mesure de leurs caractéristiques fonctionnelles. A cet effet, le besoin de disposer d’informations sur l’exécution du système à évaluer est manifeste. C’est dans ce cadre qu’une nouvelle approche d’observation des SMA est proposée. Les résultats de ces observations sont exploités pour construire une abstraction du système sous forme d’un modèle, lequel est étudié pour définir les mesures de performances. L’analyse se focalise sur deux caractéristiques essentielles, à la base de la dynamique et de la socialité des SMA : la communication et l’organisation. Les expérimentations de la solution proposée portent sur deux applications multi-agents. La première est une application de diagnostic des pannes dans un environnement industriel et la seconde est une application de pilotage et de gestion de la production dans les chaînes logistiques. / This thesis focuses on the issue of MultiAgent Systems (MAS) evaluation. The MAS own characteristics, namely autonomy, distribution, dynamicity and sociality, have greatly contributed to the expansion of their application scope; but in return they made their analysis more difficult. Thus, evaluation methods in classic computer systems are insufficient to analyse MAS, since they do not take into account their specificities. The objective of this thesis is to provide a generic approach for the evaluation of MAS by measuring their functional characteristics. To this end, the need for information about the execution of the system to be evaluated is evident. In this context, a new approach to observe MAS is proposed. The results of these observations are exploited to build an abstraction model of the system which is studied in order to define performance metrics. The analysis focuses on two key characteristics, at the basis on the dynamics and sociality in MAS: communication and organization. The experiments of the proposed solution are performed on two multiagent applications. The first is an application of fault diagnosis in an industrial environment and the second is an application of control and production planning in supply chains.

Les codes identifiants ont été introduits en 1998 par Karpovsky, Chakrabarty et Levitin. Un code identifiant est un sous-graphe tel que chaque sommet est identifié de manière unique par les sommets du code qui l'entourent. Il existe plusieurs variantes de ces codes, dont notamment une version colorée dans laquelle les sommets sont identifiés par les couleurs dans leur voisinage. Dans cette thèse, nous cherchons en particulier à construire un cycle le plus grand possible qui admette une coloration identifiante, étant donné un nombre de couleurs fixé. Nous avons aussi étudié le problème des codes identifiants sur une classe particulière de graphes orientés : les tournois. Dans une seconde partie, nous avons aussi étudié deux jeux particuliers. Le premier est une généralisation des jeux octaux - qui se jouent normalement sur un tas - aux graphes. Plus précisemment, le jeu 0.33 ; chaque joueur peut retirer un ou deux sommets voisins d'un graphe, sans déconnecter ce dernier. Le premier qui ne peut plus jouer perd. Nous avons été capable de caractériser les issues de ce jeu dans des classes de graphes particulières, les étoiles subdivisées et les bi-étoiles subdivisées. Le second jeu est appelé le jeu du Pompier (Firefighter). Il consiste à arrêter un feu qui se propage dans un graphe en protégeant des sommets à chaque tour. Nous avons résolu une conjecture sur ce jeu, et introduit la version online, pour laquelle nous avons pu donner des résultats d'approximation. / Identifying codes were introduced in 1998 by Karpovsky, Chakrabarty and Levitin. An identifying code is a subgraph such that each vertex is uniquely identified by the vertices in its neighborhood. There are several variants of these codes, including a colored version where the vertices are identified by the colors in their neighborhood. In this phd, we want to build an identifying coloring of a large cycle, given a fixed number of colors. We also studied identified codes in a certain class of oriented graphs: tournaments. We have also studied some topics in the game theory. The first one is a generalization of octal games, where we play on a graph instead of a heap. More precisely, the 0.33 game; each player can remove one or two vertices in a graph, with no disconnection allowed. The first player who cannot play loses. We studied this game in some graph classes: subdivided stars and subdivided bistars. The other game is called the Firefighter game. It's a one player game, where this one wants to contain a spreading fire in a graph. We solved a conjecture about this game, and introduced the online version of the game, for which we found some approximation results.

Title: Computational Complexity in Graph Theory Author: Eva Jelínková Department: Department of Applied Mathematics Supervisor: Prof. RNDr. Jan Kratochvíl, CSc., Department of Applied Mathematics Abstract: We address problems from graph theory, especially from the computational complexity point of view. In the first part of the thesis we address the computational complexity of problems related to Seidel's switch- ing of graphs. We prove that the problem to decide if a given graph can be switched to contain at most a given number of edges is NP-complete, even for graphs with bounded density. We thus partially answer a question of Matoušek and Wagner [Discrete Comput. Geom. 52, no. 1, 2014]. We also describe infinitely many graphs H such that it is NP-complete to decide if a given graph is switching-equivalent to a graph that does not contain H as an induced subgraph. We thus close an open problem of Kratochvíl, Nešetřil and Zýka [Annals of Discrete Math. 51, 1992]. In the second part of the thesis we address the topic of matchings under preferences. We focus on the housing market problem, in particular, on the model with duplicate houses. We present a 2-approximation algorithm for the maximum number of satisfied agents when the preference lists of agents are trichotomic. On the other hand, we...

Este trabalho investigou diferenças entre grupos etários distintos nas associações semânticas de palavras em três estudos. O primeiro buscou apresentar e discutir pesquisas que avaliaram a organização e processamento léxico-semânticos entre grupos de crianças, adultos e idosos. O segundo comparou as associações semânticas de palavras entre 247 crianças de 3ª série, 108 adultos jovens universitários e 57 idosos. O terceiro analisou comparativamente os grafos computacionais das associações semânticas de palavras entre 57 crianças de 3ª série, 57 adultos jovens universitários e os 57 idosos supracitados. Nos estudos empíricos observou-se que a força de associação entre alvo e associada mais frequente foi maior para as crianças do que para adultos e idosos. Os tamanhos de conjunto significativo e total dos alvos foram, em média, menores para os idosos e o índice de diversidade de respostas foi maior no grupo dos adultos. A modelagem de grafos indicou que crianças possuem redes de associação de palavras com maiores distâncias entre os nós e menor número de nós, ligações e agrupamentos. Adultos e idosos apresentaram redes com estruturas semelhantes. Assim, entende-se que essas associações sofrem reestruturações e ajustes da infância para a idade adulta e que na velhice ocorrem apenas mudanças quantitativas. Limitações e implicações dos estudos para a área são discutidas. / This research investigated differences in three age groups on semantic word associations in three studies. The first one aimed to present and discuss research that investigated the organization and processing of semantic elements in children, adults, and elderly. . The second one compared semantic word associations among 247 third grade children, 108 young college students adults, and 57 elderly. The third study compared semantic associations through graph analysis of 57 third grade children, 57 college students adults, and the 57 elderly cited above. The empirical studies demonstrated that the strength of the first associate to each target was higher for children compared to adults and elderly. The target’s total and meaning set sizes were lower for elderly and the response’s diversity index was higher for adults. Graph analysis suggested that children have semantic word association’s networks with greater inter-node distances and less number of nodes, connections, and clusters. Adults and elderly showed networks with similar structures. It was hypothesized that these associations pass by restructuring and tuning processes from childhood to adulthood and that after the 60 years old only quantitative changes occur. Limitations and contributions to the field are discussed.

SILVA, Aline Alves da. Decomposição e largura em árvore de grafos planares livres de ciclos pares induzidos. 2007. 80 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2007. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T17:52:45Z No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T12:18:29Z (GMT) No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Made available in DSpace on 2016-07-13T12:18:29Z (GMT). No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) Previous issue date: 2007 / The definitions of tree decomposition and treewidth were introduced by Robertson and Seymour in their series of papers on graph minors, published during the nineties. It is known that many NP-hard problems can be polynomially solved if a tree decomposition of bounded treewidth is given. So, it is of interest to bound the treewidth of certain classes of graphs. In this context, the planar graphs seem to be specially challenging because, in despite of having many known bounded metrics (for example, chromatic number), they have unbounded treewidth. So, an alternative approach is to restrict ourselves to a subclass of planar graphs. In this work, we investigate the class of even-hole-free planar graphs. We show that if G is an even-hole-free planar graph, then it does not contain a subdivision of the 10£10 grid. So, if the grid minors of G are obtained from subdivisions, then G has treewidth at most 49. Furthermore, two polynomial, non-exact algorithms to compute a tree decomposition of a even-hole-free planar graph are given, both based on known characterizations of even-hole-free graphs. In the ¯rst one, a tree decomposition is built from basic graphs by concatenating the tree decomposition of small pieces via the clique, k-stars (k = 1; 2; 3) and 2-join cutsets. In the second one, a tree decomposition is built by including one by one the vertices of G, following their bi-simplicial order. / Os conceitos de Decomposição em Árvore e Largura em Árvore foram introduzidos por Robertson e Seymour em sua série de artigos sobre menores de grafos, publicados ao longo da década de 90. Sabe-se que muitos problemas NP - difíceis podem ser resolvidos polinomialmente para um grafo G, dada uma decomposição em Árvore de G de largura limitada. Logo, limitar a largura em árvore de uma classe de grafos torna-se um objeto de estudo de grande interesse. Neste contexto, a classe dos grafos planares se mostra bastante intrigante, uma vez que, apesar de possuir outras métricas limitadas em valores baixos (por exemplo, número cromático), não possui largura em árvore limitada. Desta forma, uma alternativa é restringir a classe estudada para uma subclasse dos grafos planares. Neste trabalho, nós investigamos a classe dos grafos planares livres de buracos pares. Nós mostramos que se G é um grafo planar livre de buracos pares, então ele não contém uma subdivisão de uma grade 10 £ 10. Portanto, se os menores grades de G são obtidos de subdivisões G tem largura em árvore no máximo 49. Além disso, dois algoritmos não exatos polinomiais para computar uma decomposição em árvore de um grafo planar livre de buracos pares são apresentados, ambos baseados em caracterizações conhecidas de tal classe de grafos. No primeiro algoritmo, uma decomposição em árvore é construída a partir de grafos básicos pela concatenação de decomposições em árvores de pedaços pequenos via os cortes clique, k-estrelas (k = 1; 2; 3) e 2-join. No segundo, uma decomposição em árvore é construída pela inclusão dos vértices de G um a um, seguindo sua ordem bi-simplicial.

A graph G is maximal nontraceable (MNT) (maximal nonhamiltonian (MNH)) if G is not traceable (hamiltonian), i.e. does not contain a hamiltonian path (cycle), but G+xy is traceable (hamiltonian) for all nonadjacent vertices x and y in G. A graph G is hypohamiltonian if G is not hamiltonian, but every vertex deleted subgraph G -u of G is hamiltonian. A graph which is maximal nonhamiltonian and hypohamiltonian is called maximal hypohamiltonian (MHH). Until recently, not much has appeared in the literature about MNT graphs, although there is an extensive literature on MNH graphs. In 1998 Zelinka constructed two classes of MNT graphs and made the conjecture, which he later retracted, that every MNT graph belongs to one of these classes. We show that there are many different types of MNT graphs that cannot be constructed by Zelinka's methods. Although we have not been able to characterize MNT graphs in general, our attempt at characterizing MNT graphs with a specified number of blocks and cut-vertices enabled us to construct infinite families of non-Zelinka MNT graphs which have either two or three blocks. We consider MNT graphs with toughness less than one, obtaining results leading to interesting constructions of MNT graphs, some based on MHH graphs. One result led us to discover a non-Zelinka MNT graph of smallest order, namely of order 8. We also present examples of MNTgraphs with toughness at least one, including an infinite family of 2-connected, claw-free graphs. We find a lower bound for the size of 2-connected MNT graphs of order n. We construct an infinite family of 2-connected cubic MNT graphs of order n, using MHH graphs as building blocks. We thus find the minimum size of 2-connected MNT graphs for infinitely many values of n. We also present a construction, based on MHH graphs, of an infinite family of MNT graphs that are almost cubic. We establish the minimum size of MNT graphs of order n, for all except 26 values of n, and we present a table of MNT graphs of possible smallest size for the excluded 26 values of n. / Mathematical Sciences / PHD (MATHEMATICS)

Orientador: Prof. Dr. Rafael de Mattos Grisi / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2015. / Este trabalho apresenta uma introdução ao estudo da Teoria dos Grafos, com um dicionário visual e um histórico detalhado das origens deste ramo da matemática. Será dada uma ênfase especial ao estudo de grafos planares e na imersão de grafos em outras superfícies. Por fim, é apresentado um plano de aula para o professor interessado em introduzir o ensino de grafos a alunos do ensino fundamental e médio. / This paper presents an introduction to the study of Graph Theory, with a visual dictionary and a detailed history of the origins of this branch of mathematics. It will be given a special emphasis on the study of planar graphs and also in immersion graphs in other surfaces. Finally, we present a lesson plan for teacher interested in introducing the teaching of graphs to students of primary and secondary education.

Este trabalho investigou diferenças entre grupos etários distintos nas associações semânticas de palavras em três estudos. O primeiro buscou apresentar e discutir pesquisas que avaliaram a organização e processamento léxico-semânticos entre grupos de crianças, adultos e idosos. O segundo comparou as associações semânticas de palavras entre 247 crianças de 3ª série, 108 adultos jovens universitários e 57 idosos. O terceiro analisou comparativamente os grafos computacionais das associações semânticas de palavras entre 57 crianças de 3ª série, 57 adultos jovens universitários e os 57 idosos supracitados. Nos estudos empíricos observou-se que a força de associação entre alvo e associada mais frequente foi maior para as crianças do que para adultos e idosos. Os tamanhos de conjunto significativo e total dos alvos foram, em média, menores para os idosos e o índice de diversidade de respostas foi maior no grupo dos adultos. A modelagem de grafos indicou que crianças possuem redes de associação de palavras com maiores distâncias entre os nós e menor número de nós, ligações e agrupamentos. Adultos e idosos apresentaram redes com estruturas semelhantes. Assim, entende-se que essas associações sofrem reestruturações e ajustes da infância para a idade adulta e que na velhice ocorrem apenas mudanças quantitativas. Limitações e implicações dos estudos para a área são discutidas. / This research investigated differences in three age groups on semantic word associations in three studies. The first one aimed to present and discuss research that investigated the organization and processing of semantic elements in children, adults, and elderly. . The second one compared semantic word associations among 247 third grade children, 108 young college students adults, and 57 elderly. The third study compared semantic associations through graph analysis of 57 third grade children, 57 college students adults, and the 57 elderly cited above. The empirical studies demonstrated that the strength of the first associate to each target was higher for children compared to adults and elderly. The target’s total and meaning set sizes were lower for elderly and the response’s diversity index was higher for adults. Graph analysis suggested that children have semantic word association’s networks with greater inter-node distances and less number of nodes, connections, and clusters. Adults and elderly showed networks with similar structures. It was hypothesized that these associations pass by restructuring and tuning processes from childhood to adulthood and that after the 60 years old only quantitative changes occur. Limitations and contributions to the field are discussed.

La classe des graphes sans P5, c'est-à-dire des graphes ne contenant pas de chaîne induite à cinq sommets, est d'un intérêt particulier en théorie des graphes. Il s'agit en effet de la plus petite classe définie par un seul sous-graphe connexe interdit pour laquelle on ignore encore s'il existe un algorithme polynomial permettant de résoudre le problème du stable maximum. Or ce problème, dont on sait qu'il est difficile en général, est d'une grande importance en pratique (problèmes de planification, d'allocation de registres dans un processeur, biologie moléculaire...). Dans cette thèse, nous commençons par dresser un état de l'art complet des méthodes utilisées pour résoudre le problème dans des sous-classes de graphes sans P5, puis nous étudions et résolvons ce problème dans une sous-classe particulière, la classe des graphes sans P5 3-colorables. Nous apportons également des solutions aux problèmes de la reconnaissance et de la coloration de ces graphes, chaque fois en temps linéaire. Enfin, nous définissons, caractérisons et sommes capables de reconnaître les graphes "chain-probe", qui sont les graphes auxquels il est possible de rajouter des arêtes entre certains sommets de sorte qu'ils soient bipartis et sans P5. Les problèmes de ce type proviennent de la génétique et ont également des applications en intelligence artificielle. / The class of P5-free graphs, namely the graphs without induced chains with five vertices, is of particular interest in graph theory. Indeed, it is the smallest class defined by only one forbidden connected induced subgraph for which the complexity of the Maximum Independent Set problem is unknown. This problem has many applications in planning, CPU register allocation, molecular biology... In this thesis, we first give a complete state of art of the methods used to solve the problem in P5-free graphs subclasses; then we study and solve this problem in a particular subclass, the class of 3-colorable P5-free graphs. We also bring solutions to recognition and coloring problems of these graphs, each time in linear time. Finally, we define, characterize, and are able to recognize "chain-probe" graphs, namely the graphs for which we can add edges between particular vertices such that the resulting graph is bipartite and P5-free. Problems of this type come from genetics and have application in I.A.