Banca de DEFESA: SAULO ANTONIO DE LIMA MATOS

Uma banca de DEFESA de DOUTORADO foi cadastrada pelo programa.
STUDENT : SAULO ANTONIO DE LIMA MATOS
DATE: 03/10/2023
TIME: 10:00
LOCAL: https://conferenciaweb.rnp.br/sala/defesa-doutorado-saulomatos
TITLE:

Invariants and Neighborhood Structures for 1-factorizations of complete graphs

KEY WORDS:

1-factorizations, Graph Theory, Isomorphism, Invariants, Edge coloring, Neighborhoods, Round-robin tournaments

PAGES: 65
BIG AREA: Ciências Exatas e da Terra
AREA: Ciência da Computação
SUBÁREA: Teoria da Computação
SPECIALTY: Análise de Algoritmos e Complexidade de Computação
SUMMARY:

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. Furthermore, 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.

COMMITTEE MEMBERS:
Presidente - 2115562 - RAFAEL AUGUSTO DE MELO
Interno - 2250653 - TIAGO DE OLIVEIRA JANUARIO
Externo ao Programa - 311515 - CELSO DA CRUZ CARNEIRO RIBEIRO - UFBAExterno à Instituição - VINICIUS FERNANDES DOS SANTOS - UFMG
Externo à Instituição - MARCIO COSTA SANTOS - UFMG
Externo à Instituição - SEBASTIÁN ALBERTO URRUTIA