Campo DC | Valor | Idioma |
dc.creator | Matos, Saulo Antônio de Lima | - |
dc.date.accessioned | 2024-08-14T15:39:13Z | - |
dc.date.available | 2024-08-14T15:39:13Z | - |
dc.date.issued | 2023-10-03 | - |
dc.identifier.citation | 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. | pt_BR |
dc.identifier.uri | https://repositorio.ufba.br/handle/ri/39862 | - |
dc.description.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. | pt_BR |
dc.description.sponsorship | Fundação de Amparo a Pesquisa do Estado da Bahia - FAPESB | pt_BR |
dc.language | eng | pt_BR |
dc.publisher | Universidade Federal da Bahia | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Teoria dos grafos | pt_BR |
dc.subject | Isomorfismo | pt_BR |
dc.subject.other | Graph theory | pt_BR |
dc.subject.other | Isomorphism | pt_BR |
dc.title | Invariants and neighborhood structures for 1-factorizations of complete graphs | pt_BR |
dc.title.alternative | Invariantes e estruturas de vizinhança para fatorações 1 de gráficos completos | pt_BR |
dc.type | Tese | pt_BR |
dc.contributor.referees | Ribeiro, Celso da Cruz Carneiro | - |
dc.publisher.program | Programa de Pós-Graduação em Ciência da Computação (PGCOMP) | pt_BR |
dc.publisher.initials | UFBA | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO | pt_BR |
dc.contributor.advisor1 | Melo, Rafael Augusto de | - |
dc.contributor.advisor1ID | https://orcid.org/0000-0003-4300-0097 | pt_BR |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/4117373032501782 | pt_BR |
dc.contributor.advisor-co1 | Januario, Tiago de Oliveira | - |
dc.contributor.advisor-co1ID | https://orcid.org/0000-0003-0237-1596 | pt_BR |
dc.contributor.advisor-co1Lattes | http://lattes.cnpq.br/7975984954243833 | pt_BR |
dc.contributor.referee1 | Melo, Rafael Augusto de | - |
dc.contributor.referee1ID | http://orcid.org/0000-0003-4300-0097 | pt_BR |
dc.contributor.referee1Lattes | http://lattes.cnpq.br/4117373032501782 | pt_BR |
dc.contributor.referee2 | Januario, Tiago de Oliveira | - |
dc.contributor.referee2ID | https://orcid.org/0000-0003-0237-1596 | pt_BR |
dc.contributor.referee2Lattes | http://lattes.cnpq.br/7975984954243833 | pt_BR |
dc.contributor.referee3 | Urrutia, Sebastián Alberto | - |
dc.contributor.referee3Lattes | http://lattes.cnpq.br/6852348890045723 | pt_BR |
dc.contributor.referee4 | Santos, Vinicius Fernandes dos | - |
dc.contributor.referee4ID | https://orcid.org/0000-0002-4608-4559 | pt_BR |
dc.contributor.referee4Lattes | http://lattes.cnpq.br/6270626469557436 | pt_BR |
dc.contributor.referee5 | Santos, Marcio Costa | - |
dc.contributor.referee5ID | https://orcid.org/0000-0002-5452-0226 | pt_BR |
dc.contributor.referee5Lattes | http://lattes.cnpq.br/4258661430014987 | pt_BR |
dc.creator.ID | https://orcid.org/0000-0002-9046-5703 | pt_BR |
dc.creator.Lattes | http://lattes.cnpq.br/9937443999469263 | pt_BR |
dc.description.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. | pt_BR |
dc.publisher.department | Instituto de Computação - IC | pt_BR |
dc.contributor.refereesLattes | http://lattes.cnpq.br/3614186131432854 | pt_BR |
dc.type.degree | Doutorado | pt_BR |
Aparece nas coleções: | Tese (PGCOMP)
|