Bolsa 19/25410-3 - Otimização combinatória, Grafos - BV FAPESP
Processo: 19/25410-3
Beneficiário: Pedro Olímpio Nogueira de Oliveira Pinheiro
Assunto(s): Otimização combinatória Grafos Algoritmos Biologia computacional Programação linear
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)