https://repositorio.ufba.br/handle/ri/39862
Tipo: | Tese |
Título: | Invariants and neighborhood structures for 1-factorizations of complete graphs |
Título(s) alternativo(s): | Invariantes e estruturas de vizinhança para fatorações 1 de gráficos completos |
Autor(es): | Matos, Saulo Antônio de Lima |
Primeiro Orientador: | Melo, Rafael Augusto de |
metadata.dc.contributor.advisor-co1: | Januario, Tiago de Oliveira |
metadata.dc.contributor.referee1: | Melo, Rafael Augusto de |
metadata.dc.contributor.referee2: | Januario, Tiago de Oliveira |
metadata.dc.contributor.referee3: | Urrutia, Sebastián Alberto |
metadata.dc.contributor.referee4: | Santos, Vinicius Fernandes dos |
metadata.dc.contributor.referee5: | Santos, Marcio Costa |
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. |
Abstract: | A 1-factorization is a partition of the edge set of a graph into perfect matchings. The concept of 1-factorization is of great interest due to its applications in modeling sports tournaments. Two 1-factorizations are said to be isomorphic (belong to the same isomorphism class) if there exists a bijection between their sets of vertices that transforms one into the other. The non-isomorphic 1-factorization search space is a graph in which each isomorphism class is represented by a vertex and each edge that connects the vertices $\mathcal{F}_a$ and $\mathcal{F}_b$ corresponds to a move in a neighborhood structure, which from a 1-factorization isomorphic to $\mathcal{F}_a$ generates a 1-factorization isomorphic to $\mathcal{F}_b$. An invariant of a 1-factorization is a property that depends only on its structure such that isomorphic 1-factorizations are guaranteed to have equal invariant values. An invariant is complete when any two non-isomorphic 1-factorizations have distinct invariant values. This thesis reviews seven invariants used to distinguish non-isomorphic 1-factorizations of $K_{2n}$ (complete graph with an even number of vertices). Additionally, considering that the invariants available in the literature are not complete, we propose two new ones, denoted lantern profiles and even-size bichromatic chains. The invariants are compared regarding their sizes and calculation time complexity. Furthermore, we conduct computational experiments to assess their ability to distinguish non-isomorphic 1-factorizations. To accomplish that we use the sets of non-isomorphic 1-factorizations of $K_{10}$ and $K_{12}$, as well as the sets of non-isomorphic perfect 1-factorizations of $K_{14}$ and $K_{16}$. We also consider algorithmic and computational aspects for exploring the generalized partial team swap (GPTS) neighborhood, a neighborhood structure for round-robin sports scheduling problems recently proposed in the literature. In this regard, we present a framework to explore the GPTS neighborhood. Finally, a discussion is presented on how this neighborhood structure increases the connectivity of the search space defined by non-isomorphic 1-factorizations of $K_{2n}$ (for $8 \le 2n \le 12$) when compared to other neighborhood structures. |
Palavras-chave: | Teoria dos grafos Isomorfismo |
CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO |
Idioma: | eng |
País: | Brasil |
Editora / Evento / Instituição: | Universidade Federal da Bahia |
Sigla da Instituição: | UFBA |
metadata.dc.publisher.department: | Instituto de Computação - IC |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação (PGCOMP) |
Citação: | MATOS, Saulo Antônio de Lima. Invariants and Neighborhood Structures for 1-factorizations of complete graphs. 2023. 79 f. Tese (Doutorado em Ciência da Computação) Instituto de Computação, Universidade Federal da Bahia, Salvador (Bahia), 2023. |
Tipo de Acesso: | Acesso Aberto |
URI: | https://repositorio.ufba.br/handle/ri/39862 |
Data do documento: | 3-Out-2023 |
Aparece nas coleções: | Tese (PGCOMP) |
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Tese_Saulo_Matos.pdf | Tese de doutorado de Saulo Antonio de Lima Matos. PGCOMP - UFBA | 1,35 MB | 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.