Busca avançada
Ano de início
Entree

Partição de grafos eulerianos em circuitos

Processo: 19/25410-3
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de março de 2020
Vigência (Término): 28 de fevereiro de 2021
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Zanoni Dias
Beneficiário:Pedro Olímpio Nogueira de Oliveira Pinheiro
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Otimização combinatória   Grafos   Algoritmos   Biologia computacional   Programação linear

Resumo

Neste trabalho vamos propor algoritmos para resolver o problema de particionar o conjunto de arestas de um grafo em subconjuntos, de forma que o subgrafo induzido por cada subconjunto de arestas é um circuito, visando maximizar a quantidade de subconjuntos da partição. Projetaremos também algoritmos para uma variação desse problema em que as arestas do grafo possuem cores (pretas ou cinza) e os subgrafos induzidos pelos subconjuntos de arestas são circuitos alternados, isto é, arestas consecutivas no circuito têm cores diferentes. Investigaremos aplicações desses problemas de particionamento ao problema da ordenação por reversão, o qual tem grande relevância na área de biologia computacional no estudo da distância evolutiva entre espécies. Desenvolveremos modelos de programação linear inteira que permitam resolver os problemas de forma exata e algoritmos que utilizem heurísticas construtivas e meta-heurísticas para obter boas soluções. Por fim, vamos realizar experimentos para comparar o desempenho dos algoritmos que apresentaremos. (AU)