Busca avançada
Ano de início
Entree


Partição de grafos eulerianos em circuitos

Texto completo
Autor(es):
Pedro Olímpio Nogueira de Oliveira Pinheiro
Número total de Autores: 1
Tipo de documento: Dissertação de Mestrado
Imprenta: Campinas, SP.
Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
Data de defesa:
Membros da banca:
Zanoni Dias; Kelly Cristina Poldi; Rafael Crivellari Saliba Schouery
Orientador: Cid Carvalho de Souza; Zanoni Dias
Resumo

Uma partição em circuitos de um grafo consiste em particionar o conjunto de arestas desse grafo em subconjuntos não vazios, de forma que o grafo induzido por cada subconjunto seja um circuito no grafo original. Todo grafo euleriano pode ser particionado em circuitos, porém, diversas partições de tamanhos diferentes podem ser viáveis. No problema da Máxima Partição em Circuitos, o objetivo é encontrar uma partição em circuitos de um grafo euleriano com a maior cardinalidade possível. Para esse problema, propomos heurísticas gulosas, heurísticas que resolvem o modelo de Programação Linear Inteira (PLI) proposto por Caprara, Panconesi e Rizzi, com apenas um subconjunto das variáveis e sem geração de colunas, e algoritmos exatos que resolvem o mesmo modelo PLI com geração de colunas. Para o modelo PLI, foi necessária a criação de um algoritmo para resolver o problema de pricing. Criamos um benchmark de instâncias e executamos diversos experimentos para avaliar esses algoritmos. Verificamos que a heurística com uso de PLI obtém os melhores resultados, obtendo solução ótima em quase 70% das instâncias utilizadas. Também abordamos o problema da Máxima Partição em Circuitos Alternados, em que as arestas do grafo possuem uma cor, entre preta e cinza, e os circuitos devem ser alternados, ou seja, arestas seguidas devem ter cores diferentes. Para esse problema, propomos heurísticas gulosas, uma heurística baseada na meta-heurística Busca Tabu e algoritmos exatos com uso de PLI. Criamos outro benchmark de instâncias, executamos experimentos e comparamos os resultados obtidos com resultados de algoritmos encontrados na literatura. Executar o algoritmo exato usando as variáveis e limitantes obtidos pelas heurísticas foi o método que mostrou melhores resultados, superando os algoritmos da literatura e obtendo o resultado ótimo em 96.4% das instâncias usadas. Além disso, usamos as soluções do problema da Máxima Partição em Circuitos Alternados para resolver problemas de Rearranjo de Genomas e os nossos métodos também apresentaram os melhores resultado (AU)

Processo FAPESP: 19/25410-3 - Partição de grafos eulerianos em circuitos
Beneficiário:Pedro Olímpio Nogueira de Oliveira Pinheiro
Modalidade de apoio: Bolsas no Brasil - Mestrado