Full text
| |
| Author(s): |
Pedro Olímpio Nogueira de Oliveira Pinheiro
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | Campinas, SP. |
| Institution: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Defense date: | 2021-10-08 |
| Examining board members: |
Zanoni Dias;
Kelly Cristina Poldi;
Rafael Crivellari Saliba Schouery
|
| Advisor: | Cid Carvalho de Souza; Zanoni Dias |
| Abstract | |
A cycle partition of a graph consists of partitioning the set of edges of that graph into non-empty subsets, so that the graph induced by each subset is a cycle in the original graph. Every Eulerian graph can be partitioned into cycles, however, several partitions of different sizes may be viable. In the Maximum Eulerian Cycle Decomposition problem, the objective is to find a cycle partition of an Eulerian graph with the greatest possible cardinality. For this problem, we propose greedy heuristics, heuristics that solve the Integer Linear Programming (ILP) model proposed by Caprara, Panconesi and Rizzi, with only a subset of the variables and no column generation, and exact algorithms that solve the same ILP model with column generation. For the ILP model, it was necessary to create an algorithm to solve the pricing problem. We create a benchmark of instances and run several experiments to evaluate these algorithms. We verified that the ILP based heuristic obtains the best results, obtaining an optimal solution in almost 70% of the instances used. We also approached the problem of Maximum Alternating-Cycle Decomposition, in which the edges of the graph have a color, between black and gray, and the cycle must be alternated, that is, consecutive edges must have different colors. For this problem, we propose greedy heuristics, a heuristic based on the Tabu Search meta-heuristic and exact algorithms using ILP. We create another benchmark of instances, run experiments and compare the results with results from algorithms found in the literature. Running the exact algorithm using the variables and bounds obtained by the heuristics was the method that showed the best results, surpassing the algorithms in the literature and obtaining the optimal result in 96.4% of the instances used. Furthermore, we use Maximum Alternating-Cycle Decomposition solutions to solve Genome Rearrangement problems and our methods also showed the best results (AU) | |
| FAPESP's process: | 19/25410-3 - Partition of Eulerian graphs in circuits |
| Grantee: | Pedro Olímpio Nogueira de Oliveira Pinheiro |
| Support Opportunities: | Scholarships in Brazil - Master |