Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/39006| Título: | Enumeração de bicliques e cliques: grafos bipartidos de permutação e grafos 2-finos próprios |
| Título(s) alternativo(s): | Enumerating bicliques and cliques: bipartite permutation and proper 2-thin graphs |
| Autor(es): | Godinho, Gabriel Henrique Kwiatkovski |
| Orientador(es): | Groshaus, Marina Esther |
| Palavras-chave: | Teoria dos grafos Algorítmos computacionais Complexidade computacional Grafos bipartidos Graph theory Computer algorithms Computational complexity Bipartite graphs |
| Data do documento: | 16-Jun-2025 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Curitiba |
| Citação: | GODINHO, Gabriel Henrique Kwiatkovski. Enumeração de bicliques e cliques: grafos bipartidos de permutação e grafos 2-finos próprios. 2025. Trabalho de Conclusão de Curso (Bacharelado em Engenharia de Computação) - Universidade Tecnológica Federal do Paraná, Curitiba, 2025. |
| Resumo: | Este trabalho apresenta dois algoritmos voltados à enumeração de subestruturas importantes em classes específicas de grafos. O primeiro algoritmo é dedicado à listagem de todas as bicliques em grafos bipartidos de permutação, também conhecidos como grafos 2-finos próprios independentes. O segundo algoritmo propõe uma abordagem para enumerar todas as cliques em grafos 2-finos próprios, explorando suas propriedades estruturais para garantir eficiência. Ambos os algoritmos são acompanhados por provas formais de correção e análise de complexidade, contribuindo para o avanço no estudo de classes de grafos. |
| Abstract: | This work presents two algorithms designed to enumerate key substructures in specific classes of graphs. The first algorithm focuses on listing all bicliques in bipartite permutation graphs, also known as proper 2-thin independent graphs. The second algorithm introduces a method for enumerating all cliques in proper 2-thin graphs, exploiting their structural properties to achieve efficiency. Both algorithms are supported by formal proofs of correctness and complexity analyses, contributing to the advancement of research on structured graph classes. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/39006 |
| Aparece nas coleções: | CT - Engenharia de Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| enumeracaobicliquesgrafospermutacao.pdf | 472,91 kB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
