Uma heurística construtiva gulosa eficiente para o problema do conjunto dominante independente mínimo

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorCasanova, Dalcimar-
Autor(es): dc.contributorhttp://lattes.cnpq.br/4155115530052195-
Autor(es): dc.contributorBarbosa, Marco Antonio de Castro-
Autor(es): dc.contributorhttps://orcid.org/0000-0001-9674-2348-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5794615482009389-
Autor(es): dc.contributorCasanova, Dalcimar-
Autor(es): dc.contributorhttp://lattes.cnpq.br/4155115530052195-
Autor(es): dc.contributorOliva, Jefferson Tales-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5086431818930800-
Autor(es): dc.contributorNagano, Marcelo Seido-
Autor(es): dc.contributorhttps://orcid.org/0000-0002-0239-1725-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9832648827661734-
Autor(es): dc.contributorBarbosa, Marco Antonio de Castro-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5794615482009389-
Autor(es): dc.creatorAlessi, Andre Eduardo-
Data de aceite: dc.date.accessioned2025-08-29T12:14:15Z-
Data de disponibilização: dc.date.available2025-08-29T12:14:15Z-
Data de envio: dc.date.issued2024-07-03-
Data de envio: dc.date.issued2024-07-03-
Data de envio: dc.date.issued2024-04-05-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/33837-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1091560-
Descrição: dc.descriptionThe Minimum Independent Dominating Set (MIDS) problem is an optimization problem in graph theory whose objective is to find the smallest subset of vertices of a graph that is both independent and dominating. Being a NP-hard problem, there is no polynomial-time algorithm that can find an optimal solution for it, unless P = NP. To address problem instances where exact algorithms are intractable, some heuristic and metaheuristic approaches were proposed for this problem in the literature, aiming to find a good solution in tractable time. These approaches mainly focus on the local search phase, trying to improve a given initial solution. However, little effort has been spent on the construction phase, i.e., to try to build an already good initial solution. To fill this gap, in this work, we propose an efficient greedy constructive heuristic for the MIDS problem, with the objective of finding good-quality initial solutions without applying an intensification procedure. To evaluate the performance of our approach, we did a comparative study with the state-of-the-art heuristic approach for the MIDS problem, called MAE-PB. We show that, in average, our greedy method can find better solution quality in less time than MAE-PB, in addition to having little variability in solution quality and having no parameters to tune.-
Descrição: dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)-
Descrição: dc.descriptionO Problema do Conjunto Independente Dominante Mínimo (PCIDM) é um problema de otimização em teoria de grafos que tem como objetivo determinar o menor subconjunto de vértices de um grafo tal que ele seja ao mesmo tempo independente e dominante. Tratando-se de um problema NP-difícil, não há um algoritmo que encontre uma solução ótima para o problema em tempo polinomial, a não ser que P = NP. Para encontrar soluções de qualidade satisfatória em tempo tratável, abordagens heurísticas e metaheurísticas para esse problema foram propostas na literatura, as quais focam principalmente na fase de busca local, buscando melhorar uma solução inicial. Entretanto, não se buscou um bom método construtivo, para gerar boas soluções iniciais. Para preencher essa lacuna, neste trabalho é proposta uma heurística construtiva gulosa eficiente para o PCIDM, cujo desempenho é avaliado por meio de um estudo comparativo com o método estado-da-arte MAE-PB. O método proposto, de forma geral, encontra melhores soluções em menos tempo do que o MAE-PB, além de possuir baixa variabilidade na qualidade das soluções encontradas e não ter parâmetros para ajustar.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherPato Branco-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherPrograma de Pós-Graduação em Engenharia Elétrica-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightshttps://creativecommons.org/licenses/by/4.0/-
Palavras-chave: dc.subjectOtimização matemática-
Palavras-chave: dc.subjectTeoria dos grafos-
Palavras-chave: dc.subjectAlgorítmos-
Palavras-chave: dc.subjectHeurística-
Palavras-chave: dc.subjectMathematical optimization-
Palavras-chave: dc.subjectGraph theory-
Palavras-chave: dc.subjectAlgorithms-
Palavras-chave: dc.subjectHeuristic-
Palavras-chave: dc.subjectCNPQ::ENGENHARIAS::ENGENHARIA ELETRICA-
Palavras-chave: dc.subjectEngenharia/Tecnologia/Gestão-
Título: dc.titleUma heurística construtiva gulosa eficiente para o problema do conjunto dominante independente mínimo-
Título: dc.titleAn efficient greedy constructive heuristic for the minimum independent dominating set problem-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.