
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 | Casanova, Dalcimar | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/4155115530052195 | - |
| Autor(es): dc.contributor | Barbosa, Marco Antonio de Castro | - |
| Autor(es): dc.contributor | https://orcid.org/0000-0001-9674-2348 | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/5794615482009389 | - |
| Autor(es): dc.contributor | Casanova, Dalcimar | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/4155115530052195 | - |
| Autor(es): dc.contributor | Oliva, Jefferson Tales | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/5086431818930800 | - |
| Autor(es): dc.contributor | Nagano, Marcelo Seido | - |
| Autor(es): dc.contributor | https://orcid.org/0000-0002-0239-1725 | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/9832648827661734 | - |
| Autor(es): dc.contributor | Barbosa, Marco Antonio de Castro | - |
| Autor(es): dc.contributor | http://lattes.cnpq.br/5794615482009389 | - |
| Autor(es): dc.creator | Alessi, Andre Eduardo | - |
| Data de aceite: dc.date.accessioned | 2025-08-29T12:14:15Z | - |
| Data de disponibilização: dc.date.available | 2025-08-29T12:14:15Z | - |
| Data de envio: dc.date.issued | 2024-07-03 | - |
| Data de envio: dc.date.issued | 2024-07-03 | - |
| Data de envio: dc.date.issued | 2024-04-05 | - |
| Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/33837 | - |
| Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1091560 | - |
| Descrição: dc.description | The 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.description | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) | - |
| Descrição: dc.description | O 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.format | application/pdf | - |
| Idioma: dc.language | pt_BR | - |
| Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
| Publicador: dc.publisher | Pato Branco | - |
| Publicador: dc.publisher | Brasil | - |
| Publicador: dc.publisher | Programa de Pós-Graduação em Engenharia Elétrica | - |
| Publicador: dc.publisher | UTFPR | - |
| Direitos: dc.rights | openAccess | - |
| Direitos: dc.rights | https://creativecommons.org/licenses/by/4.0/ | - |
| Palavras-chave: dc.subject | Otimização matemática | - |
| Palavras-chave: dc.subject | Teoria dos grafos | - |
| Palavras-chave: dc.subject | Algorítmos | - |
| Palavras-chave: dc.subject | Heurística | - |
| Palavras-chave: dc.subject | Mathematical optimization | - |
| Palavras-chave: dc.subject | Graph theory | - |
| Palavras-chave: dc.subject | Algorithms | - |
| Palavras-chave: dc.subject | Heuristic | - |
| Palavras-chave: dc.subject | CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA | - |
| Palavras-chave: dc.subject | Engenharia/Tecnologia/Gestão | - |
| Título: dc.title | Uma heurística construtiva gulosa eficiente para o problema do conjunto dominante independente mínimo | - |
| Título: dc.title | An efficient greedy constructive heuristic for the minimum independent dominating set problem | - |
| Tipo de arquivo: dc.type | livro digital | - |
| Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT | |
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: