ANÁLISE DO PROBLEMA DE F-SUBDIVISÃO
Resumo
Uma subdivisão de um digrafo F, também chamada de F-subdivisão, é um digrafo obtido de F ao substituir cada arco (a,b) de F por um (a,b)-caminho direcionado. No artigo estudado, foi considerado o problema de F-SUBDIVISÃO para um digrafo F fixo, onde a entrada é um digrafo D e cuja questão é “D contém uma subdivisão de F como um subdigrafo?”. Um vértice v em um digrafo F é grande, quando o seu grau de saída ou de entrada é pelo menos 3; ou ambos o seu grau de saída e de entrada são iguais a 2. Já uma grade cilíndrica de ordem k consiste de k ciclos direcionados concêntricos e 2k caminhos direcionados conectando os ciclos em direções alternantes. O teorema(Kawabarayashi and Kreutzer [3]) diz que para qualquer inteiro positivo, existe um inteiro f(k) tal que dado qualquer digrafo, em tempo polinomial, pode-se obter tanto uma grade cilíndrica de ordem k como um menor borboleta, ou uma árvore de decomposição direcionada de largura máxima f(k). Em [2], os autores mencionam que F-SUBDIVISÃO é de tempo polinomial resolvível em digrafos de largura de árvore direcionada limitada. Depois, mencionam sem provar que: (*) (para qualquer digrafo planar F com nenhum vértice grande, há um inteiro k_F tal que a grade cilíndrica de ordem k_F contém uma F-subdivisão.). Este trabalho, considera que (*) é falso e tem como objetivo caracterizar os digrafos F tais que (*) não seja válido. Para isto, deseja-se caracterizar F-modelos para ajudar nesta tarefa. Em suma, a pesquisa obteve como resultado a seguinte propriedade para dois digrafos H e G quaisquer, H é menor de G sse G tem H-modelo. [1] J. Bang-Jensen, F. Havet e A. Maia, “Finding a subdivision of a digraph”, Theoretical Comp. Sci. 562, 2015, 283–303. [2] F. Havet, A. Maia e B. Mohar, “Finding a subdivision of a prescribed digraph of order 4”, Journal of Graph Theory 87, 2018, 536–560. [3] K. Kawarabayashi et S. Kreutzer. The directed grid theorem. arXiv:1411.5681 [cs.DM]Publicado
2019-01-14
Edição
Seção
XXXVII Encontro de Iniciação Científica
Licença
Autores que publicam nesta revista concordam com os seguintes termos:
a. Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License que permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista.
b. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
c. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.