Invariants and Neighborhood Structures for 1-Factorizations of Complete Graphs

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.




Rafael Augusto de Melo




Tiago de Oliveira Januario


Membro Titular Externo 1 (com afiliação)


Sebastián Alberto Urrutia


Link para o curriculum lattes


Membro Titular Externo 2 (com afiliação)


Vinicius Fernandes dos Santos


Link para o curriculum lattes


Membro Titular Interno 1 ou Titular Externo 3 (com afiliação)


Marcio Costa Santos


Link para o curriculum lattes


Membro Titular Interno 2 ou Titular Externo 4 (com afiliação)


Celso da Cruz Carneiro Ribeiro


Link para o curriculum lattes


Membro Suplente Externo 1 (com afiliação)


Jesus Ossian da Cunha Silva


Link para o curriculum lattes


Membro Suplente Externo 2 (com afiliação)


Hugo Harry Frederico Ribeiro Kramer


Link para o curriculum lattes


Membro Suplente Interno 1 ou Suplente Externo 3 (com afiliação)


Frederico Araujo Durão


Link para o curriculum lattes


Membro Suplente Interno 2 ou Suplente Externo 4 (com afiliação)


Roberto Freitas Parente


Link para o curriculum lattes


Data da defesa


03 Oct, 2023


Horário da defesa


10:00 AM



Data da Defesa: 
03/10/2023 - 10:00
Tipo de Defesa: 
Defesa de Doutorado