Admissibilidade em grafos: geração de casos e análise por modelos de aprendizado

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorCunha, Luís Felipe Ignácio-
Autor(es): dc.contributorAraújo, Leandro Santiago de-
Autor(es): dc.contributorSouza, Uéverton dos Santos-
Autor(es): dc.creatorSouza, Felipe Silva-
Data de aceite: dc.date.accessioned2025-01-03T11:41:04Z-
Data de disponibilização: dc.date.available2025-01-03T11:41:04Z-
Data de envio: dc.date.issued2024-10-04-
Data de envio: dc.date.issued2024-10-04-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/34920-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/919750-
Descrição: dc.descriptionUm grafo G é t-admissível se possuir uma árvore geradora T tal que quaisquer vértices adjacentes em G estejam a uma distância no máximo t em T, caso em que T é chamada de árvore t-geradora de G. Denotamos como índice de extensão de G, ou σ(G), o menor valor t tal que G é t-admissível. Apesar de haver um decisor polinomial para t = 2, o problema é NP-completo para t ≥ 4, enquanto a variante t = 3 permanece em aberto décadas após sua proposição. O presente trabalho elabora algoritmos para criar grafos com índices de extensão e/ou fatores de admissibilidade conhecidos. De fato, mostramos como construir um dataset fornecendo o parâmetro σ de todas as 12.111 classes de isomorfismo de grafos conexos de 3 a 8 vértices e discutimos métodos de geração aleatória para grafos t-admissíveis e não t-admissíveis de tamanho arbitrário. Essas técnicas nos possibilitam estudar o problema sob a perspectiva do aprendizado de máquina. Mostramos como modelos lazy e eager podem ter alta performance sob interessantes condições de teste, mesmo para instâncias no espectro NP-completo do problema.-
Descrição: dc.descriptionA graph G is t-admissible if it has a spanning tree T such that any adjacent vertices in G are at a distance of at most t in T, in which case T is called a tree t-spanner of G. We denote as stretch index of G, or σ(G), the smallest value t such that G is t-admissible. Despite having a polynomial decider for t = 2, the problem is NP-complete for t ≥ 4, while the t = 3 variant remains open decades after its proposal. The present work elaborates algorithms to create graphs with known stretch indexes and/or admissibility factors. Indeed, we show how to build a dataset providing the parameter σ of all 12, 111 isomorphism classes of connected graphs from 3 to 8 vertices and discuss random generation methods for t-admissible and non-t-admissible graphs of arbitrary size. These techniques give us the ability to study the problem from machine learning’s perspective. We show how both lazy and eager models can have high performance under interesting testing conditions, even for instances in the NP-complete spectrum of the problem.-
Descrição: dc.description36 f.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languageen-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectCiência da computação-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectAlgoritmo em grafos-
Palavras-chave: dc.subjectAprendizado de máquina-
Palavras-chave: dc.subjectAprendizado de máquina-
Palavras-chave: dc.subjectAlgoritmo em grafos-
Palavras-chave: dc.subjectCiência da computação-
Palavras-chave: dc.subjectComputer science-
Palavras-chave: dc.subjectGraph theory-
Palavras-chave: dc.subjectGraph algorithm-
Palavras-chave: dc.subjectMachine learning-
Título: dc.titleAdmissibilidade em grafos: geração de casos e análise por modelos de aprendizado-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.