Use este identificador para citar ou linkar para este item:
http://repositorio.ufc.br/handle/riufc/84981| Tipo: | TCC |
| Título: | Subdivisões de orientações do grafo bipartido completo K2,3 |
| Autor(es): | Serra, Philipe Medeiros |
| Orientador: | Oliveira, Ana Karolinna Maia de |
| Palavras-chave em português: | Teoria da computação;Complexidade computacional;Teoria dos digrafos;Subdivisões de digrafos;K-Linkage |
| Palavras-chave em inglês: | Theory of computation;Computational complexity;Digraph theory;Subdivisions of digraphs;K-Linkage |
| CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Data do documento: | 2026 |
| Citação: | SERRA, Philipe Medeiros. Subdivisões de orientações do grafo bipartido completo K2,3. 2026. 13 f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2026. |
| Resumo: | Neste trabalho, exploramos o problema de encontrar uma subdivisão de um dígrafo F em um dígrafo D. com o objetivo de identificar instâncias polinomiais e NP-completas do mesmo. Mais especificamente, focamos nos casos em que F e uma orientação do K2,3, na tentativa de ter uma visão mais clara sobre uma conjectura a respeito do problema em grafos planares. Apresentamos todas as possíveis orientações do K2,3 e os casos que o problema pode ser resolvido de maneira polinomial, utilizando fluxos ou Teorema do Grid Direcionado. A complexidade de apenas um caso permanece em aberto. |
| Abstract: | In this work, we explore the problem of finding a subdivision of a digraph F in a digraph D, with the goal of identifying polynomial-time and NP-complete instances of the problem. More specifically, we focus on the cases where F is an orientation of K2,3, in an attempt to gain a clearer understanding of a conjecture regarding the problem in planar graphs. We present all possible orientations of K2,3 and the cases where the problem can be solved in polynomial time, using flow techniques or the Directed Grid Theorem. The complexity of only one case remains open. |
| URI: | http://repositorio.ufc.br/handle/riufc/84981 |
| Currículo Lattes do(s) Autor(es): | http://lattes.cnpq.br/4333313674264382 |
| Currículo Lattes do Orientador: | http://lattes.cnpq.br/3309825374177429 |
| Tipo de Acesso: | Acesso Aberto |
| Aparece nas coleções: | CIÊNCIA DA COMPUTAÇÃO - Monografias |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 2026_tcc_pmserra.pdf | 416 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.