Advanced search
Start date

Partition of Eulerian graphs in circuits

Grant number: 19/25410-3
Support Opportunities:Scholarships in Brazil - Master
Effective date (Start): March 01, 2020
Effective date (End): February 28, 2021
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Zanoni Dias
Grantee:Pedro Olímpio Nogueira de Oliveira Pinheiro
Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil


In this paper we will propose algorithms to solve the problem of partitioning the edge set of a graph into subsets, so that the subgraph induced by each subset of edges is a circuit, aiming to maximize the number of subsets of the partition. We will also design algorithms for a variation of this problem where the edges of the graph have colors (black or gray) and the subgraphs induced by the subsets of edges are alternating circuits, that is, consecutive edges in the circuit have different colors. We will investigate applications of these partitioning problems to the reverse ordering problem, which has great relevance in the area of computational biology in the study of evolutionary distance between species. We will develop models of integer linear programming to solve problems exactly and algorithms that use constructive heuristics and metaheuristics to obtain good solutions. Finally, we will conduct experiments to compare the performance of the algorithms we will present. (AU)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
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., . (19/25410-3, 13/08293-7, 19/27331-3, 17/12646-3, 15/11937-9)
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
PINHEIRO, Pedro Olímpio Nogueira de Oliveira. Partition of eulerian graphs in circuits. 2021. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.

Please report errors in scientific publications list using this form.