Detalhes bibliográficos
| Ano de defesa: |
2023 |
| Autor(a) principal: |
Matos, Saulo Antônio de Lima
 |
| Orientador(a): |
Melo, Rafael Augusto de
|
| Banca de defesa: |
Ribeiro, Celso da Cruz Carneiro
,
Melo, Rafael Augusto de
,
Januario, Tiago de Oliveira
,
Urrutia, Sebastián Alberto
,
Santos, Vinicius Fernandes dos
,
Santos, Marcio Costa |
| Tipo de documento: |
Tese
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
eng |
| Instituição de defesa: |
Universidade Federal da Bahia
|
| Programa de Pós-Graduação: |
Programa de Pós-Graduação em Ciência da Computação (PGCOMP)
|
| Departamento: |
Instituto de Computação - IC
|
| País: |
Brasil
|
| Palavras-chave em Português: |
|
| Área do conhecimento CNPq: |
|
| Link de acesso: |
https://repositorio.ufba.br/handle/ri/39862
|
Resumo: |
Uma 1-fatoração é uma partição do conjunto de arestas de um grafo em emparelhamentos perfeitos. O conceito de 1-fatoração é de grande interesse devido às suas aplicações na modelagem de torneios esportivos. Duas 1-fatorações são ditas isomorfas (pertencem a mesma classe de isomorfismo) se existir uma bijeção entre seus conjuntos de vértices que transforme uma na outra. O espaço de busca de 1-fatorações não isomorfas é um grafo em que cada classe de isomorfismo é representada por um vértice e cada aresta que conecta os vértices $\mathcal{F}_a$ e $\mathcal{F}_b$ corresponde a um movimento em uma estrutura de vizinhança, que a partir de uma 1-fatoração isomorfa a $\mathcal{F}_a$ gera uma 1-fatoração isomorfa a $\mathcal{F}_b$. Uma invariante de uma 1-fatoração é uma propriedade que depende apenas de sua estrutura, de modo que 1-fatorações isomorfas possuem valores de invariantes iguais. Uma invariante é completa quando quaisquer duas 1-fatorações não isomorfas têm valores invariantes distintos. Essa tese analisa sete invariantes utilizadas para distinguir 1-fatorações não isomorfas de $K_{2n}$ (grafos completos com quantidade par de vértices). Considerando que as invariantes disponíveis na literatura não são completas, propomos duas novas invariantes, denominadas lantern profiles e even-size bichromatic chains. As invariantes são comparadas quanto aos seus tamanhos e à complexidade computacional do seu cálculo. Além disso, realizamos experimentos computacionais para avaliar suas capacidades de distinguir 1-fatorações não isomorfas. Para tal, utilizamos os conjuntos de 1-fatorações não isomorfas de $K_{10}$ e $K_{12}$, bem como os conjuntos de 1-fatorações perfeitas não isomorfas de $K_{14}$ e $K_{16}$. Também consideramos aspectos algorítmicos e computacionais para explorar a vizinhança generalized partial team swap (GPTS), uma estrutura de vizinhança para problemas de planejamento de tabelas de torneios round-robin recentemente proposta na literatura. Nesse sentido, apresentamos algoritmos para explorar sistematicamente a vizinhança GPTS. Além disso, é apresentada uma discussão sobre como esta estrutura de vizinhança aumenta a conectividade do espaço de busca definido por 1-fatorações não isomorfas de $K_{2n}$ (para $8 \le 2n \le 12$) quando comparada a outras estruturas de vizinhança. Por fim, experimentos computacionais preliminares foram conduzidos para avaliar o desempenho da vizinhança GPTS, utilizando como estudo de caso o Weighted Carry-Over Effects Value Minimization Problem. |
