Publicações

Intimamente associados à ciência da computação, grafos são objeto de incessante esforço de pesquisa acadêmica. Podem ser convenientemente pensados como modelos de redes de relacionamentos, ilustrados, por vezes, como pontos conectados por linhas retas ou curvas. A rigor, os objetos conectados são chamados vértices, enquanto às linhas que indicam um relacionamento chamamos arestas.

Entre os problemas da teoria dos grafos está a busca, num grafo em particular, de árvores que possuam determinado conjunto de propriedades. Aqui, árvores são apenas grafos conexos e acíclicos. Encontrar uma árvore que contemple todos os vértices de um grafo, por exemplo, é tarefa simples com o conhecimento teórico de hoje. A esse tipo de árvore, nota-se, chamamos geradoras.

Mas, haverá árvore geradora alguma num grafo G em que cada par de vizinhos de G está separado por, no máximo, t arestas? Eis o problema da admissibilidade de árvores t-geradoras. Pode-se ainda perguntar o menor valor t tal que o grafo observado seja t-admissível, isto é, admita alguma árvore t-geradora. Este valor é chamado índice de extensão do grafo.

Este trabalho foi resultado de uma iniciação científica realizada na graduação e submetido na categoria de trabalho oral ao LV SBPO, onde tive a honra de apresentá-lo ao público em 9 de novembro de 2023, na cidade de São José dos Campos, SP. O texto teve coautoria de dois professores do IC-UFF.

São apresentados algoritmos para síntese de grafos, permitindo a construção de bases de dados que possam servir outros estudos no tema. Os resultados, obtidos de implementações em linguagem C/C++, são apresentados junto a discussões de outros tópicos associados, como isomorfismos e representação de grafos.

Está agora disponível nos anais do evento, acessível pelo endereço abaixo.

DOI: https://doi.org/10.59254/sbpo-2023-174918

Keywords: Árvore t-geradora; Geração de grafos; Sequências de Prüfer.

Este texto foi baseado em meu TCC e produzido junto aos mesmos professores do trabalho anterior.

Segue as discussões no mesmo tema, apresentando novos algoritmos para síntese de grafos t-admissíveis e avaliando a eficácia de modelos de aprendizado aplicados ao problema, usando os grafos gerados para alimentar o treinamento e a avaliação dos modelos. São empregados alguns dos mais notáveis modelos, como regressão logística e random forest, com uso de pacotes como scikit-learn e pandas através da linguagem Python.

Foi publicado em inglês pelo Journal of Computational Science.

DOI: https://doi.org/10.1016/j.jocs.2024.102281

Keywords: Graph algorithms; Tree t-spanners; Machine learning.