
Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
| Metadados | Descrição | Idioma |
|---|---|---|
| Autor(es): dc.contributor | Cunha, Luís Felipe Ignácio | - |
| Autor(es): dc.contributor | Araújo, Leandro Santiago de | - |
| Autor(es): dc.contributor | Souza, Uéverton dos Santos | - |
| Autor(es): dc.creator | Souza, Felipe Silva | - |
| Data de aceite: dc.date.accessioned | 2025-01-03T11:41:04Z | - |
| Data de disponibilização: dc.date.available | 2025-01-03T11:41:04Z | - |
| Data de envio: dc.date.issued | 2024-10-04 | - |
| Data de envio: dc.date.issued | 2024-10-04 | - |
| Fonte completa do material: dc.identifier | https://app.uff.br/riuff/handle/1/34920 | - |
| Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/919750 | - |
| Descrição: dc.description | Um 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.description | A 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.description | 36 f. | - |
| Formato: dc.format | application/pdf | - |
| Idioma: dc.language | en | - |
| Direitos: dc.rights | Open Access | - |
| Direitos: dc.rights | CC-BY-SA | - |
| Palavras-chave: dc.subject | Ciência da computação | - |
| Palavras-chave: dc.subject | Teoria dos grafos | - |
| Palavras-chave: dc.subject | Algoritmo em grafos | - |
| Palavras-chave: dc.subject | Aprendizado de máquina | - |
| Palavras-chave: dc.subject | Aprendizado de máquina | - |
| Palavras-chave: dc.subject | Algoritmo em grafos | - |
| Palavras-chave: dc.subject | Ciência da computação | - |
| Palavras-chave: dc.subject | Computer science | - |
| Palavras-chave: dc.subject | Graph theory | - |
| Palavras-chave: dc.subject | Graph algorithm | - |
| Palavras-chave: dc.subject | Machine learning | - |
| Título: dc.title | Admissibilidade em grafos: geração de casos e análise por modelos de aprendizado | - |
| Tipo de arquivo: dc.type | Trabalho de conclusão de curso | - |
| Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF | |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: