«« Voltar
Análise de Algoritmos para Problemas de Otimização em Grafos usando Decomposição em Árvore e Modular
Protocolo do SIGProj:   284434.1430.126085.30102017
De:20/02/2018  à  20/12/2019
 
Coordenador-Extensionista
  Vagner Pedrotti
Instituição
  UFMS - Universidade Federal de Mato Grosso do Sul
Unidade Geral
  FACOM - Faculdade de Computação
Unidade de Origem
  CPQ - Comissão Setorial de Pesquisa
Resumo da Ação de Extensão
  A solução de problemas de otimização em grafos é uma técnica frequentemente utilizada para a melhoria de processos, cujos objetivos são redução de custos, tempo ou outros recursos envolvidos. Entretanto, muitos dos problemas de interesse prático são modelados por problemas em grafos que se mostram computacionalmente complexos (NP-difícies) e os algoritmos genéricos são inviáveis para a solução dos mesmos. Para contornar esta dificuldade, a pesquisa se concentrou em propor alternativas, sejam elas algoritmos mais eficientes para classes específicas de grafos que espera-se sejam comuns nas instâncias da aplicação; o uso de heurísticas que, de alguma forma, acelerem a solução do problema; algoritmos aproximados e probabilísticos, ou simplesmente, heurísticas. Neste contexto, este projeto de pesquisa deseja-se estudar ao menos dois problemas com diferentes abordagens. O primeiro é a pesquisa por heurísticas para acelerar a solução de problemas de otimização em grafos que consistem em encontrar um subconjunto ótimo de vértices om uma propriedade especificada. O segundo é o uso da decomposição modular em classes especiais de grafos para solução de alguns problemas de otimização. Como um subproblema do primeiro deles, deseja-se avaliar soluções heurísticas para encontrar uma decomposição em árvore de um grafo minimizando o tamanho de cada nó. Tal decomposição é utilizada omo entrada do primeiro problema.
Palavras-chave
   treewidth, combinatória discreta, lógica de segunda ordem, decomposição modular
Público-Alvo
  
Situação
  Atividade EM ANDAMENTO
Contato
  
«« Voltar