Use este identificador para citar ou linkar para este item: http://www.repositorio.ufc.br/handle/riufc/21822
Título: Número de dominação romana em grafos
Título em inglês: Roman domination number in graphs
Autor(es): Araújo, Samuel Nascimento de
Orientador(es): Sampaio, Rudini Menezes
Palavras-chave: Computabilidade e Complexidade
Teoria dos Grafos
Data do documento: 2016
Citação: ARAÚJO, S. N. (2016)
Resumo: 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.
Abstract: 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.
Descrição: 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.
URI: http://www.repositorio.ufc.br/handle/riufc/21822
Aparece nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2016_dis_snaraújo.pdf1,35 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.