Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/84981| Type: | TCC |
| Title: | Subdivisões de orientações do grafo bipartido completo K2,3 |
| Authors: | Serra, Philipe Medeiros |
| Advisor: | Oliveira, Ana Karolinna Maia de |
| Keywords in Brazilian Portuguese : | Teoria da computação;Complexidade computacional;Teoria dos digrafos;Subdivisões de digrafos;K-Linkage |
| Keywords in English : | Theory of computation;Computational complexity;Digraph theory;Subdivisions of digraphs;K-Linkage |
| Knowledge Areas - CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Issue Date: | 2026 |
| Citation: | 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. |
| Abstract in Brazilian Portuguese: | 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 |
| Author's Lattes: | http://lattes.cnpq.br/4333313674264382 |
| Advisor's Lattes: | http://lattes.cnpq.br/3309825374177429 |
| Access Rights: | Acesso Aberto |
| Appears in Collections: | CIÊNCIA DA COMPUTAÇÃO - Monografias |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2026_tcc_pmserra.pdf | 416 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.