Algoritmos para o problema da árvore geradora mínima generalizado

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorOchi, Luiz Satoru-
Autor(es): dc.contributorCPF:31609080822-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9171815778534257-
Autor(es): dc.contributorMacambira, Elder Magalhães-
Autor(es): dc.contributorCPF:34512909722-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2240491564472936-
Autor(es): dc.contributorRibeiro, Celso da Cruz Carneiro-
Autor(es): dc.contributorCPF:34620081022-
Autor(es): dc.contributorhttp://lattes.cnpq.br/3614186131432854-
Autor(es): dc.contributorBarboza, Eduardo Uchoa-
Autor(es): dc.contributorCPF:85462487922-
Autor(es): dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4721785E2-
Autor(es): dc.contributorAragão, Marcus Vinicius Soledade Poggi de-
Autor(es): dc.contributorCPF:34769521122-
Autor(es): dc.contributorhttp://lattes.cnpq.br/0833253899619895-
Autor(es): dc.contributorMateus, Geraldo Robson-
Autor(es): dc.contributorCPF:34870906322-
Autor(es): dc.contributorhttp://lattes.cnpq.br/6289602045034353-
Autor(es): dc.creatorFerreira, Cristiane Maria Santos-
Data de aceite: dc.date.accessioned2024-07-11T17:36:12Z-
Data de disponibilização: dc.date.available2024-07-11T17:36:12Z-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2008-03-05-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2007-05-04-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/17107-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/753638-
Descrição: dc.descriptionDado um grafo G cujos vértices estão divididos em grupos, o Problema da Árvore Geradora Mínimo Generalizado consiste em encontrar uma árvore que cubra um vértice de cada grupo de G, de forma a minimizar a soma dos custos das arestas. As principais aplicações desse problema são encontradas na área de síntese de redes de telecomunicações. Nesse trabalho, são propostas versões da meta-heurísitca GRASP que utilizam mais de um algoritmo construtivo de forma adaptativa, além de mecanismos adicionais de aprimoramento, com reconexão de caminhos e busca local iterada. Testes comparativos com instâncias apresentadas na literatura indicaram que o uso adaptativo de diferentes algoritmos construtivos é promissor. Também foi verificado que as versões GRAP que utilizam mecanismos adicionais apresentam melhores resultados que as demais. Os algoritmos propostos resultaram em soluções melhores que algumas das melhores soluções conhecidas, em um tempo computacional razoavelmente baixo. Também foi implementado um algoritmo de geração de cortes baseado em uma formulação para o Problema de Steiner em Grafos Direcionado. Com esse algoritmo, foi possível encontrar limites duais para 82 instâncias em aberto. São apresentadas ainda regras para o pré-processamento de instâncias euclideanas, baseadas no conceito de Distância Battleneck. Em média, tais regras propiciaram a redução das instâncias para 14% do número de arestas em relação aos grafos originais.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherPrograma de Pós-Graduação em Computação-
Publicador: dc.publisherComputação-
Direitos: dc.rightsAcesso Aberto-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectCiência da computação-
Palavras-chave: dc.subjectInteligência artificial-
Palavras-chave: dc.subjectOtimização combinatória-
Palavras-chave: dc.subjectGRASP-
Palavras-chave: dc.subjectMetaheurística-
Palavras-chave: dc.subjectGrafo-
Palavras-chave: dc.subjectAlgoritmo-
Palavras-chave: dc.subjectProgramação inteira-
Palavras-chave: dc.subjectOtimização em redes-
Palavras-chave: dc.subjectComputer science-
Palavras-chave: dc.subjectMetaheuristics-
Palavras-chave: dc.subjectInteger programming-
Palavras-chave: dc.subjectNetwork optimization-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO-
Título: dc.titleAlgoritmos para o problema da árvore geradora mínima generalizado-
Tipo de arquivo: dc.typeDissertação-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.