Partição de grafos eulerianos em circuitos

• Processo: 19/25410-3
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2020
• Data de Término da vigência: 28 de fevereiro de 2021
• Área de 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
• Palavra(s)-Chave do Pesquisador: Partição em Grafos | Otimização Combinatória

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)

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

PINHEIRO, PEDRO OLIMPIO; ALEXANDRINO, ALEXSANDRO OLIVEIRA; OLIVEIRA, ANDRE RODRIGUES; DE SOUZA, CID CARVALHO; DIAS, ZANONI; SETUBAL, JC; SILVA, WM. Heuristics for Breakpoint Graph Decomposition with Applications in Genome Rearrangement Problems. ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2020, v. 12558, p. 12-pg., 2020-01-01. (19/25410-3, 13/08293-7, 19/27331-3, 17/12646-3, 15/11937-9)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

PINHEIRO, Pedro Olímpio Nogueira de Oliveira. Partição de grafos eulerianos em circuitos. 2021. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.