Invariants and Neighborhood Structures for 1-Factorizations of Complete Graphs

Enviado por hugo.chaves em qua, 30/08/2023 - 14:11

Nome completo do aluno

Saulo Antonio de Lima Matos

Título do trabalho

Invariants and neighborhood structures for 1-factorizations of complete graphs

Resumo do trabalho

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.

Orientador

Rafael Augusto de Melo

Co-orientador

Tiago de Oliveira Januario

Membro Titular Externo 1 (com afiliação)

Sebastián Alberto Urrutia

Link para o curriculum lattes

http://lattes.cnpq.br/6852348890045723

Membro Titular Externo 2 (com afiliação)

Vinicius Fernandes dos Santos

Link para o curriculum lattes

http://lattes.cnpq.br/6270626469557436