ARAUJO, Samuel Nascimento de. Número de dominação romana em grafos. 2016. 51 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2016. / Submitted by Anderson Silva Pereira (anderson.pereiraaa@gmail.com) on 2017-01-25T17:42:43Z No. of bitstreams: 1 2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2017-01-26T20:23:42Z (GMT) No. of bitstreams: 1 2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5) / Made available in DSpace on 2017-01-26T20:23:42Z (GMT). No. of bitstreams: 1 2016_dis_snaraújo.pdf: 1382335 bytes, checksum: fd12ba0538ea370f6fd3606ec0b79031 (MD5) Previous issue date: 2016 / In a Roman domination of a graph, vertices are assigned a value from {0,1,2} in such a way that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. The Roman domination number is the minimum possible sum of all values in such an assignment. In this dissertation, we show the history of the problem and prove that the Roman domination number is NP-Complete even for induced subgraphs of grids and it is APX-hard even for bipartite graphs with maximum degree 4. We also prove that the Roman domination number is fixed parameter tractable for graphs with bounded local treewidth, as graphs with bounded maximum degree or bounded genus (like planar graphs or toroidal graphs). We also obtain complexity results when we consider digraphs as an input for the problem such as bipartite tournaments and planar digraphs. / No problema de dominação romana de um grafo, os vértices são atribuídos um valor de {0,1,2}, de tal maneira que cada vértice atribuído o valor 0 é adjacente a um vértice que foi atribuído o valor 2. O número de dominação romana é a menor soma possível de todos os valores dos vértices em tal atribuição. Nesta dissertação apresentamos a história do problema, e provamos que o número dominação romana é NP-Completo mesmo para subgrafos induzidos de grids e é APX-difícil mesmo para grafos bipartidos com o grau máximo 4. Nós também provamos que o número de dominação romana é tratável por parâmetro fixo para grafos com treewidth local limitada, como grafos com grau máximo limitado ou genus limitado (como por exemplo grafos planares). Nós também obtivemos resultados de complexidade quando consideramos digrafos como entrada para o problema, tais como torneios bipartidos e digrafos planares.

Submitted by Algacilda Conceição (algacilda@sibi.ufrj.br) on 2018-03-26T15:35:35Z No. of bitstreams: 1 38068.pdf: 674548 bytes, checksum: eaf0ac625b3c867a529c8633a152972a (MD5) / Made available in DSpace on 2018-03-26T15:35:35Z (GMT). No. of bitstreams: 1 38068.pdf: 674548 bytes, checksum: eaf0ac625b3c867a529c8633a152972a (MD5) Previous issue date: 1973-12 / Uma propriedade interessante é provada para árvore de Huffman. Quaisquer dois elementos de pesos ai e bi filhos de um mesmo pai tem a seguinte propriedade: se bi ≥ ai então Wm ≤ ai ou Wm ≥ bi onde Wm é o peso de qualquer nó da árvore. Baseado nesta propriedade, um algoritmo foi desenvolvido para atualizar dinamicamente uma árvore de Huffman, à medida que os pesos dos seus nós terminais variam. Utilizando-se este algoritmo, um modelo de um sistema adaptativo para compressão de dados foi implementado. Simulações efetuadas com diversos tipos de dados levaram a resultados interessantes. / An interesting property is proven for Huffman's tree. Any two elements with weights ai and bi sons of a same father have the following property: if bi ≥ ai then Wm ≤ ai or Wm ≥ bi where Wm is the weight of any node of the tree. Based on this property, an algorithm is developed to dynamically update Huffman's tree as weights of terminal nodes change. Using this algorithm, a model of an adaptive system for data compression is developed. Simulation using many types of data led to interesting results.